TY - GEN

T1 - Data-compression for parametrized counting problems on sparse graphs

AU - Kim, Eun Jung

AU - Serna, Maria

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Eun Jung Kim, Maria Serna, and Dimitrios M. Thilikos;

PY - 2018/12/1

Y1 - 2018/12/1

N2 - 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(k2n2) and decoding time 2O(k). This implies the existence of an 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.

AB - 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(k2n2) and decoding time 2O(k). This implies the existence of an 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.

KW - Compactor

KW - Parameterized counting

KW - Protrusion decomposition

UR - http://www.scopus.com/inward/record.url?scp=85063682760&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063682760&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2018.20

DO - 10.4230/LIPIcs.ISAAC.2018.20

M3 - Conference contribution

AN - SCOPUS:85063682760

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 20:1–20:13

BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018

A2 - Lee, Der-Tsai

A2 - Liao, Chung-Shou

A2 - Hsu, Wen-Lian

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018

Y2 - 16 December 2018 through 19 December 2018

ER -