Loading...
Loading...

Go to the content (press return)

Data-compression for parameterized counting problems on sparse graphs

Author
Kim, E. J.; Serna, M.; Thilikos, D.
Type of activity
Presentation of work at congresses
Name of edition
29th International Symposium on Algorithms and Computation
Date of publication
2018
Presentation's date
2018-12-18
Book of congress proceedings
29th International Symposium on Algorithms and Computation: ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan
First page
1
Last page
13
DOI
10.4230/LIPIcs.ISAAC.2018.20
URL
http://drops.dagstuhl.de/opus/volltexte/2018/9968/pdf/LIPIcs-ISAAC-2018-20.pdf Open in new window
Abstract
We study the concept ofcompactor, which may be seen as a counting-analogue of kernelization incounting parameterized complexity. For a functionF: S*¿Nand a parameterization¿: S*¿N, a compactor(P,M)consists of a polynomial-time computable functionP, calledcondenser, anda computable functionM, calledextractor, such thatF=M¿P, and the condensingP(x)ofxhaslength at mosts(¿(x)), for any inputx¿S*.Ifsis a polynomial function, then the compactoris said to be of polynomial-size. Although the study...
Keywords
Parameterized counting, compactor, protrusion decomposition
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

  • Kim, Eun Jung  (author and speaker )
  • Serna Iglesias, Maria Jose  (author and speaker )
  • Thilikos Touloupas, Dimitrios  (author and speaker )