2018/09/21 by Eun Jung Kim, Kim, Eun Jung, Marı́a Serna +3 · 1 citation
Computer Science · #68R10 #68W01 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems
paper · doi:10.48550/arxiv.1809.08160
openalex publication_date 2018/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the concept of compactor, which may be seen as a counting-analogue of kernelization in counting parameterized complexity. For a function F:Σ^*→ ℕ and a parameterization κ: Σ^*→ ℕ, a compactor (\sf P,\sf M) consists of a polynomial-time computable function \sf P, called condenser, and a computable function \sf M, called extractor, such that F=\sf M∘ \sf P, and the condensing \sf 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)\models ϕ. 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(k2n2) and decoding time 2O(k). This implies the existence of an \sf FPT-algorithm of running time O(n2k2)+2O(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.