Lokshtanov, Daniel
[Author];
Misra, Pranabendu
[Author];
Saurabh, Saket
[Author];
Zehavi, Meirav
[Author]
;
Daniel Lokshtanov and Pranabendu Misra and Saket Saurabh and Meirav Zehavi
[Contributor]
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
We introduce a new framework for the analysis of preprocessing routines for parameterized counting problems. Existing frameworks that encapsulate parameterized counting problems permit the usage of exponential (rather than polynomial) time either explicitly or by implicitly reducing the counting problems to enumeration problems. Thus, our framework is the only one in the spirit of classic kernelization (as well as lossy kernelization). Specifically, we define a compression of a counting problem P into a counting problem Q as a pair of polynomial-time procedures: reduce and lift. Given an instance of P, reduce outputs an instance of Q whose size is bounded by a function f of the parameter, and given the number of solutions to the instance of Q, lift outputs the number of solutions to the instance of P. When P = Q, compression is termed kernelization, and when f is polynomial, compression is termed polynomial compression. Our technical (and other conceptual) contributions can be classified into two categories: Upper Bounds. We prove two theorems: (i) The #Vertex Cover problem parameterized by solution size admits a polynomial kernel; (ii) Every problem in the class of #Planar F-Deletion problems parameterized by solution size admits a polynomial compression. Lower Bounds. We introduce two new concepts of cross-compositions: EXACT-cross-composition and SUM-cross-composition. We prove that if a #P-hard counting problem P EXACT-cross-composes into a parameterized counting problem Q, then Q does not admit a polynomial compression unless the polynomial hierarchy collapses. We conjecture that the same statement holds for SUM-cross-compositions. Then, we prove that: (i) #Min (s,t)-Cut parameterized by treewidth does not admit a polynomial compression unless the polynomial hierarchy collapses; (ii) #Min (s,t)-Cut parameterized by minimum cut size, #Odd Cycle Transversal parameterized by solution size, and #Vertex Cover parameterized by solution size minus maximum matching size, do not admit polynomial compressions unless ...