Document Open Access Logo

Exploiting c-Closure in Kernelization Algorithms for Graph Problems

Authors Tomohiro Koana , Christian Komusiewicz , Frank Sommer

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.65.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Tomohiro Koana
  • Technische Universität Berlin, Algorithmics and Computational Complexity, Germany
Christian Komusiewicz
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Frank Sommer
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany

Funding

  • Koana, Tomohiro: Supported by the Deutsche Forschungsgemeinschaft (DFG), project FPTinP, NI 369/19.
  • Sommer, Frank: Supported by the Deutsche Forschungsgemeinschaft (DFG), project MAGZ, KO 3669/4-1.

Acknowledgements

This work was started at the research retreat of the TU Berlin Algorithms and Computational Complexity group held in September 2019 at Schloss Neuhausen (Prignitz).

Cite AsGet BibTex

Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-Closure in Kernelization Algorithms for Graph Problems. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.65

Abstract

A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number c such that G is c-closed. Fox et al. [SIAM J. Comput. '20] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size k^𝒪(c), that Induced Matching admits a kernel with 𝒪(c⁷ k⁸) vertices, and that Irredundant Set admits a kernel with 𝒪(c^{5/2} k³) vertices. Our kernelization exploits the fact that c-closed graphs have polynomially-bounded Ramsey numbers, as we show.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Fixed-parameter tractability
  • kernelization
  • c-closure
  • Dominating Set
  • Induced Matching
  • Irredundant Set
  • Ramsey numbers

Metrics

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

Related Versions

References

  1. Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, and W. Henry Suters. Crown structures for vertex cover kernelization. Theory of Computing Systems, 41(3):411-430, 2007. Google Scholar
  2. Vladimir E. Alekseev, Dmitry V. Korobitsyn, and Vadim V. Lozin. Boundary classes of graphs for the dominating set problem. Discrete Mathematics, 285(1-3):1-6, 2004. Google Scholar
  3. Noga Alon and Shai Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica, 54(4):544-556, 2009. Google Scholar
  4. Reuven Bar-Yehuda and Shimon Even. A local-ratio theorem for approximating the weighted vertex cover problem. In Proceedings of the 9th International Workshop Graph-Theoretic Concepts in Computer Science (WG '83), pages 17-28. Universitätsverlag Rudolf Trauner, Linz, 1983. Google Scholar
  5. Leizhen Cai. Parameterized complexity of cardinality constrained optimization problems. The Computer Journal, 51(1):102-121, 2008. Google Scholar
  6. Marco Cesati. Perfect code is W[1]-complete. Information Processing Letters, 81(3):163-168, 2002. Google Scholar
  7. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. Journal of Algorithms, 41(2):280-301, 2001. Google Scholar
  8. Miroslav Chlebík and Janka Chlebíková. Crown reductions for the minimum weighted vertex cover problem. Discrete Applied Mathematics, 156(3):292-312, 2008. Google Scholar
  9. Benny Chor, Mike Fellows, and David W. Juedes. Linear kernels in linear time, or how to save k colors in O(n²) steps. In Proceedings of the 30th International Workshop Graph-Theoretic Concepts in Computer Science (WG '04), volume 3353 of Lecture Notes in Computer Science, pages 257-269. Springer, 2004. Google Scholar
  10. 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
  11. Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. Tight kernel bounds for problems on graphs with small degeneracy. ACM Transactions on Algorithms, 13(3):43:1-43:22, 2017. Google Scholar
  12. Konrad Dabrowski, Marc Demange, and Vadim V. Lozin. New results on maximum induced matchings in bipartite graphs and beyond. Theoretical Computer Science, 478:33-40, 2013. Google Scholar
  13. Holger Dell and Dániel Marx. Kernelization of packing problems. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12), pages 68-81. SIAM, 2012. Google Scholar
  14. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM, 61(4):23:1-23:27, 2014. Google Scholar
  15. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  16. Rodney G. Downey, Michael R. Fellows, and Venkatesh Raman. The complexity of irredundant sets parameterized by size. Discrete Applied Mathematics, 100(3):155-167, 2000. Google Scholar
  17. Paul Erdös. Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53(4):292-294, 1947. Google Scholar
  18. Rok Erman, Łukasz Kowalik, Matjaž Krnc, and Tomasz Waleń. Improved induced matchings in sparse graphs. Discrete Applied Mathematics, 158(18):1994-2003, 2010. Google Scholar
  19. Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model. SIAM Journal on Computing, 49(2):448-464, 2020. Google Scholar
  20. Shivam Garg and Geevarghese Philip. Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), pages 1152-1166. SIAM, 2016. Google Scholar
  21. Petr A. Golovach and Yngve Villanger. Parameterized complexity for domination problems on degenerate graphs. In Proceedings of the 34th International Workshop Graph-Theoretic Concepts in Computer Science (WG '08), volume 5344 of Lecture Notes in Computer Science, pages 195-205, 2008. Google Scholar
  22. Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12), pages 104-113. SIAM, 2012. Google Scholar
  23. Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2011. Google Scholar
  24. Iyad A. Kanj, Michael J. Pelsmajer, Marcus Schaefer, and Ge Xia. On the induced matching problem. Journal of Computer and System Sciences, 77(6):1058-1070, 2011. Google Scholar
  25. Christian Komusiewicz and Manuel Sorge. An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems. Discrete Applied Mathematics, 193:145-161, 2015. Google Scholar
  26. Hannes Moser and Somnath Sikdar. The parameterized complexity of the induced matching problem. Discrete Applied Mathematics, 157(4):715-727, 2009. Google Scholar
  27. Hannes Moser and Dimitrios M. Thilikos. Parameterized complexity of finding regular induced subgraphs. Journal of Discrete Algorithms, 7(2):181-190, 2009. Google Scholar
  28. George L. Nemhauser and Leslie E. Trotter. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8:232-248, 1975. Google Scholar
  29. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms, 9(1):11:1-11:23, 2012. Google Scholar
  30. Venkatesh Raman and Saket Saurabh. Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica, 52(2):203-225, 2008. Google Scholar
  31. Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in biclique-free graphs. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA ’12), volume 7501 of Lecture Notes in Computer Science, pages 802-812. Springer, 2012. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact