AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

Kernelization is a notion in parameterized complexity describing our ability to decrease the instance size using some simple (i.e. polynomial-time computable) preprocessing rules. A question often asked about parameterized problems is whether they admit preprocessing algorithms which would reduce the instance to an equivalent instance (known as a kernel) with size polynomial with respect to the parameter. The framework of Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, there are also many issues that are not addressed by this framework, including the existence of subexponential kernels and Turing kernels such as the "kernelization" of k-leaf Out Branching into a disjunction over n instances of size poly(k).

Observing that these properties and others are preserved by PPT-reductions, we define a kernelization hardness hierarchy, akin to the M- and W-hierarchy of ordinary parameterized complexity, by the PPT-closure of problems that seem likely to be fundamentally hard for kernelization. We find that several previously considered problems are complete for our fundamental hardness class WK[1], including both more expressive ones such as Min Ones q-SAT, the k-step NDTM Halting problem for single-tape machines with a binary alphabet, and Clique under a parameter of k log n, as well as seemingly more restricted problems such as Directed k-Path, and Set Cover and Exact Cover parameterized by the universe size.

Karolina Soltys

--email hidden

passcode not visible

logged in users only