Data-compression for parametrized counting problems on sparse graphs

We study the concept of compactor, which may be seen as a counting-analogue of kernelization in counting parameterized complexity. For a function F : Σ^∗ → N and a parameterization κ : Σ^∗ → N, a compactor (P, M) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F = M◦P, and the condensing P(x) of x has length at most s(κ(x)), for any input x ∈ Σ^∗. If s is a polynomial function, then the compactor is said to be of polynomial-size. Although the study on counting-analogue of kernelization is not unprecedented, it has received little attention so far. We study a family of vertex-certified counting problems on graphs that are MSOL-expressible; that is, for an MSOL-formula φ with one free set variable to be interpreted as a vertex subset, we want to count all A ⊆ V (G) where |A| = k and (G, A) |= φ. In this paper, we prove that every vertex-certified counting problems on graphs that is MSOL-expressible and treewidth modulable, when parameterized by k, admits a polynomial-size compactor on H-topological-minor-free graphs with condensing time O(k²n²) and decoding time 2^O(k⁾. This implies the existence of an FPT-algorithm of running time O(n²k²) + 2^O(k⁾. All aforementioned complexities are under the Uniform Cost Measure (UCM) model where numbers can be stored in constant space and arithmetic operations can be done in constant time.