Kim, Eun Jung ;
Serna, Maria ;
Thilikos, Dimitrios M.
DataCompression for Parametrized Counting Problems on Sparse Graphs
Abstract
We study the concept of compactor, which may be seen as a countinganalogue of kernelization in counting parameterized complexity. For a function F:Sigma^* > N and a parameterization kappa: Sigma^* > N, a compactor (P,M) consists of a polynomialtime computable function P, called condenser, and a computable function M, called extractor, such that F=M o P, and the condensing P(x) of x has length at most s(kappa(x)), for any input x in Sigma^*. If s is a polynomial function, then the compactor is said to be of polynomialsize. Although the study on countinganalogue of kernelization is not unprecedented, it has received little attention so far. We study a family of vertexcertified counting problems on graphs that are MSOLexpressible; that is, for an MSOLformula phi with one free set variable to be interpreted as a vertex subset, we want to count all A subseteq V(G) where A=k and (G,A) models phi. In this paper, we prove that every vertexcertified counting problems on graphs that is MSOLexpressible and treewidth modulable, when parameterized by k, admits a polynomialsize compactor on Htopologicalminorfree graphs with condensing time O(k^2n^2) and decoding time 2^{O(k)}. This implies the existence of an FPTalgorithm 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.
BibTeX  Entry
@InProceedings{kim_et_al:LIPIcs:2018:9968,
author = {Eun Jung Kim and Maria Serna and Dimitrios M. Thilikos},
title = {{DataCompression for Parametrized Counting Problems on Sparse Graphs}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {20:120:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9968},
URN = {urn:nbn:de:0030drops99688},
doi = {10.4230/LIPIcs.ISAAC.2018.20},
annote = {Keywords: Parameterized counting, compactor, protrusion decomposition}
}
2018
Keywords: 

Parameterized counting, compactor, protrusion decomposition 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

2018 