Document Open Access Logo

Data-Compression for Parametrized Counting Problems on Sparse Graphs

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2018.20.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Parameterized counting
  • compactor
  • protrusion decomposition

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the concept of compactor, which may be seen as a counting-analogue 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 polynomial-time 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 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 A subseteq V(G) where |A|=k and (G,A) models phi. 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(k^2n^2) and decoding time 2^{O(k)}. This implies the existence of an 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.

Cite As Get BibTex

Eun Jung Kim, Maria Serna, and Dimitrios M. Thilikos. Data-Compression for Parametrized Counting Problems on Sparse Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.20

Author Details

Eun Jung Kim
  • Université Paris-Dauphine, PSL Research University, CNRS/LAMSADE, 75016, Paris, France
Maria Serna
  • Computer Science Department & BGSMath, Universitat Politècnica de Catalunya, Barcelona, Spain
Dimitrios M. Thilikos
  • AlGCo project-team, LIRMM, Université de Montpellier, CNRS, Montpellier, France
  • and, Department of Mathematics, National and Kapodistrian University of Athens, Greece

Funding

  • Kim, Eun Jung: Supported by project ESIGMA (ANR-17-CE23-0010).
  • Serna, Maria: Partially funded by MINECO and FEDER funds under grants TIN2017-86727-C2-1-R (GRAMM) and MDM-2014-044 (BGSMath), and by AGAUR grant 2017SGR-786 (ALBCOM).
  • Thilikos, Dimitrios M.: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).

References

  1. Karl R. Abrahamson and Michael R. Fellows. Finite Automata, Bounded Treewidth and Well-Quasiordering. In Neil Robertson and Paul D. Seymour, editors, AMS Summer Workshop on Graph Minors, Graph Structure Theory, Contemporary Mathematics vol. 147, pages 539-564. American Mathematical Society, 1993. Google Scholar
  2. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12:308-340, 1991. Google Scholar
  3. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75:423-434, December 2009. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  4. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. J. ACM, 63(5):44:1-44:69, 2016. Google Scholar
  5. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. SIAM J. Discrete Math., 28(1):277-305, 2014. URL: http://dx.doi.org/10.1137/120880240.
  6. Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. Reduction algorithms for graphs of small treewidth. Inf. Comput., 167:86-119, 2001. Google Scholar
  7. Richard B. Borie, R. Gary Parker, and Craig A. Tovey. Automatic Generation of Linear-Time Algorithms from Predicate Calculus Descriptions of Problems on Recursively Constructed Graph Families. Algorithmica, 7:555-581, 1992. Google Scholar
  8. Yijia Chen, Jörg Flum, and Moritz Müller. Lower Bounds for Kernelizations and Other Preprocessing Procedures. Theory Comput. Syst., 48(4):803-839, 2011. URL: http://dx.doi.org/10.1007/s00224-010-9270-y.
  9. B. Courcelle, J.A. Makowsky, and U. Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics, 108(1):23-52, 2001. Workshop on Graph Theoretic Concepts in Computer Science. Google Scholar
  10. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. Google Scholar
  11. Bruno Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci., 109:49-82, 1993. Google Scholar
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  13. Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally Excluding a Minor. In 21st IEEE Symposium on Logic in Computer Science (LICS'07), pages 270-279. IEEE, New York, 2007. Google Scholar
  14. Babette de Fluiter. Algorithms for Graphs of Small Treewidth. PhD thesis, Dept. Computer Science, Utrecht University, 1997. Google Scholar
  15. Holger Dell. AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations. Algorithmica, 75(2):403-423, 2016. URL: http://dx.doi.org/10.1007/s00453-015-0110-y.
  16. Josep Díaz, Maria Serna, and Dimitrios M. Thilikos. Efficient algorithms for counting parameterized list H-colorings. J. Comput. System Sci., 74(5):919-937, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2008.02.004.
  17. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  18. Andrew Drucker. New Limits to Classical and Quantum Instance Compression. SIAM J. Comput., 44(5):1443-1479, 2015. URL: http://dx.doi.org/10.1137/130927115.
  19. Zdenek Dvorak, Daniel Kral, and Robin Thomas. Deciding First-Order Properties for Sparse Graphs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, pages 133-142. IEEE, Washington, DC, USA, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.20.
  20. Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing First-order Properties for Subclasses of Sparse Graphs. J. ACM, 60(5):36:1-36:24, October 2013. URL: http://dx.doi.org/10.1145/2499483.
  21. Jörg Flum and Martin Grohe. Fixed-parameter tractability, definability, and model-checking. SIAM J. Comput., 31(1):113-145, 2001. Google Scholar
  22. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  23. F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality and Kernels. In 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 503-510. ACM-SIAM, 2010. Google Scholar
  24. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470-479, 2012. Google Scholar
  25. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and Kernels. CoRR, abs/1606.05689, 2016. Revised version. URL: http://arxiv.org/abs/1606.05689.
  26. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.007.
  27. Markus Frick. Generalized Model-Checking over Locally Tree-Decomposable Classes. Theory of Computing Systems, 37(1):157-191, January 2004. Google Scholar
  28. Markus Frick and Martin Grohe. Deciding First-Order Properties of Locally Tree-Decomposable Graphs. In Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Automata, Languages and Programming, volume 1644 of LNCS, pages 72-72. Springer Berlin / Heidelberg, 1999. Google Scholar
  29. Martin Grohe. Logic, graphs, and algorithms. In Logic and Automata, pages 357-422. Amsterdam University Press, 2008. Google Scholar
  30. Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems, chapter Model Theoretic Methods in Finite Combinatorics, pages 181-206. Contemporary Mathematics, 2011. Google Scholar
  31. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding First-order Properties of Nowhere Dense Graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pages 89-98, New York, NY, USA, 2014. ACM. Google Scholar
  32. Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk. Losing treewidth by separating subsets. CoRR, abs/1804.01366, 2018. URL: http://arxiv.org/abs/1804.01366.
  33. Danny Harnik and Moni Naor. On the Compressibility of NP Instances and Cryptographic Applications. SIAM J. Comput., 39(5):1667-1713, 2010. URL: http://dx.doi.org/10.1137/060668092.
  34. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions. ACM Trans. Algorithms, 12(2):21:1-21:41, 2016. Google Scholar
  35. Eun Jung Kim, Maria Serna, and Dimitrios M. Thilikos. Data-compression for parametrized counting problems on sparse graphs. CoRR, abs/1809.08160, 2018. URL: http://arxiv.org/abs/1809.08160.
  36. Stephan Kreutzer. Algorithmic Meta-theorems. In IWPEC, pages 10-12. Springer, 2008. Google Scholar
  37. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization - Preprocessing with a Guarantee. In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx, editors, The Multivariate Algorithmic Revolution and Beyond, pages 129-161. Springer-Verlag, Berlin, Heidelberg, 2012. URL: http://dl.acm.org/citation.cfm?id=2344236.2344248.
  38. Rolf Niedermeier. Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  39. Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. Parameterized Counting Algorithms for General Graph Covering Problems. In Frank K. H. A. Dehne, Alejandro López-Ortiz, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, volume 3608 of Lecture Notes in Computer Science, pages 99-109. Springer, 2005. URL: http://dx.doi.org/10.1007/11534273_10.
  40. D. Seese. The structure of the models of decidable monadic theories of graphs. Annals of Pure and Applied Logic, 53(2):169-195, 1991. URL: http://dx.doi.org/10.1016/0168-0072(91)90054-P.
  41. Detlef Seese. Linear Time Computable Problems and First-Order Descriptions. Mathematical Structures in Computer Science, 6(6):505-526, 1996. Google Scholar
  42. Marc Thurley. Kernelizations for parameterized counting problems. In 4th international conference on Theory and applications of models of computation, TAMC'07, pages 705-714. Springer-Verlag, Berlin, Heidelberg, 2007. URL: http://portal.acm.org/citation.cfm?id=1767854.1767920.
  43. Marc Thurley. Tractability and Intractability of Parameterized Counting Problems, May 2006. Diploma thesis. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact