Data-compression for Parametrized Counting Problems on Sparse graphs

DOI10.4230/LIPICS.ISAAC.2018.20MaRDI QIDQ6307069arXivFDO

Authors Eun Jung Kim, Maria Serna, Dimitrios M. Thilikos

Publication date 21 September 2018

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2018.20

Mathematics Subject Classification ID

Logic in computer science (03B70) Enumeration in graph theory (05C30) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.DSmath.CO

Abstract: We study the concept of emph{compactor}, which may be seen as a counting-analogue of kernelization in counting parameterized complexity. For a function $F:Sigm{a}^{\ast }oBbbN$ and a parameterization $kappa:Sigm{a}^{\ast }oBbbN$, a compactor $(sfP,sfM)$ consists of a polynomial-time computable function $sfP$, called emph{condenser}, and a computable function $sfM$, called emph{extractor}, such that $F=sfMcircsfP$, and the condensing $sfP(x)$ of $x$ has length at most $s(kappa(x))$, for any input $xinSigm{a}^{\ast }.$ 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 $phi$ with one free set variable to be interpreted as a vertex subset, we want to count all $AsubseteqV(G)$ where $|A|=k$ and $(G,A)modelsphi.$ In this paper, we prove that every vertex-certified counting problems on graphs that is emph{MSOL-expressible} and emph{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 {sf 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.

This page was built for publication: Data-compression for Parametrized Counting Problems on Sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6307069)