Skip to Main content Skip to Navigation
Conference papers

Data-Compression for Parametrized Counting Problems on Sparse Graphs

Abstract : 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 2 n 2) and decoding time 2 O(k). This implies the existence of an FPT-algorithm of running time O(n 2 k 2) + 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.
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02342803
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, November 1, 2019 - 12:48:47 PM
Last modification on : Monday, August 3, 2020 - 3:38:18 AM
Document(s) archivé(s) le : Sunday, February 2, 2020 - 2:12:12 PM

File

LIPIcs-ISAAC-2018-20.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Eun Jung Kim, Maria Serna, Dimitrios M. Thilikos. Data-Compression for Parametrized Counting Problems on Sparse Graphs. ISAAC: International Symposium on Algorithms and Computation, Dec 2018, Jiaoxi, Yilan County, Taiwan. pp.20:1--20:13, ⟨10.4230/LIPIcs.ISAAC.2018.20⟩. ⟨lirmm-02342803⟩

Share

Metrics

Record views

35

Files downloads

17