A Completeness Theory for Polynomial (Turing) Kernelization. / Hermelin, Danny; Kratsch, Stefan; Soltys, Karolina; Wahlström, Magnus; Wu, Xi.

In: Algorithmica, Vol. 71, No. 3, 03.2015, p. 702-730.

Research output: Contribution to journalArticle





The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423–434, 2009) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91–106, 2011) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, some issues are not addressed by this framework, including the existence of Turing kernels such as the “kernelization” of leaf out-branching (k)(k) that outputs nn instances each of size poly(k)(k). Observing that Turing kernels are preserved by polynomial parametric transformations (PPTs), we define two kernelization hardness hierarchies by the PPT-closure of problems that seem fundamentally unlikely to admit efficient Turing kernelizations. This gives rise to the MK- and WK-hierarchies which are akin to the M- and W-hierarchies of parameterized complexity. We find that several previously considered problems are complete for the fundamental hardness class WK[1], including Min Ones dd -SAT (k)(k), Binary NDTM Halting (k)(k), Connected Vertex Cover (k)(k), and Clique parameterized by klognklog⁡n. We conjecture that no WK[1]-hard problem admits a polynomial Turing kernel. Our hierarchy subsumes an earlier hierarchy of Harnik and Naor that, from a parameterized perspective, is restricted to classical problems parameterized by witness size. Our results provide the first natural complete problems for, e.g., their class VC1VC1; this had been left open.
Original languageEnglish
Pages (from-to)702-730
Number of pages29
Issue number3
Early online date15 Jul 2014
Publication statusPublished - Mar 2015
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 23265227