Kernelization of Counting Problems

08/04/2023

∙

by   Daniel Lokshtanov, et al.

∙

0

∙

share

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: 𝗋𝖾𝖽𝗎𝖼𝖾 and 𝗅𝗂𝖿𝗍. Given an instance of P, 𝗋𝖾𝖽𝗎𝖼𝖾 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, 𝗅𝗂𝖿𝗍 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 concern both upper bounds and lower bounds.