direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Diminishable Parameterized Problems and Strict Polynomial Kernelization

Till Fluschnik (TU Berlin)

Kernelization—the mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems—plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of NP ⊈ coNP/poly. In this talk we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant.
Building on earlier work of Chen, Flum, and Müller [Theory Comput. Syst. 2011] and developing a general and remarkably simple framework, we show that a variety of FPT problems does not admit strict polynomial kernels under the weaker assumption of P ≠ NP. As an example, in this talk we show that the Multicolored Path problem does not admit a strict polynomial kernel unless P = NP. To this end, a key concept we use are diminishable problems; these are parameterized problems that allow to decrease the parameter of the input instance by at least one in polynomial time, thereby outputting an equivalent problem instance. Finally, we point out that relaxing the concept of strict kernels to kernels with a constant-factor increase of the parameter leads to a scenario in which we can prove for a number of problems that the framework is not applicable assuming that the (Strong) Exponential Time Hypothesis holds.

This is joint work with Henning Fernau, Danny Hermelin, Andreas Krebs, Hendrik Molter, and Rolf Niedermeier.


Till Fluschnik
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras