Reducing the Vertex Cover Number via Edge Contractions

Authors Paloma T. Lima , Vinicius F. dos Santos , Ignasi Sau , Uéverton S. Souza , Prafullkumar Tale



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.69.pdf
  • Filesize: 0.87 MB
  • 14 pages

Document Identifiers

Author Details

Paloma T. Lima
  • Computer Science Department, IT University of Copenhagen, Denmark
Vinicius F. dos Santos
  • Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
Ignasi Sau
  • LIRMM, Université de Montpellier, CNRS, Montpellier, France
Uéverton S. Souza
  • Instituto de Computação, Universidade Federal Fluminense, Niterói, Brazil
  • Institute of Informatics, University of Warsaw, Warsaw, Poland
Prafullkumar Tale
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

Acknowledgements

The last author would like to thank Roohani Sharma for insightful discussions.

Cite AsGet BibTex

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contractions. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.69

Abstract

The Contraction(vc) problem takes as input a graph G on n vertices and two integers k and d, and asks whether one can contract at most k edges to reduce the size of a minimum vertex cover of G by at least d. Recently, Lima et al. [MFCS 2020, JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, Contraction(vc) admits an XP algorithm running in time f(d) ⋅ n^O(d). They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results: - Contraction(vc) is W[1]-hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k + d) ⋅ n^o(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative. - It is NP-hard to decide whether an instance (G, k, d) of {Contraction(vc)} is a Yes-instance even when k = d, hence enhancing our understanding of the classical complexity of the problem. - Contraction(vc) can be solved in time 2^O(d) ⋅ n^{k - d + O(1)}. This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle’s theorem as a subroutine and hence, the f(d)-factor in the running time is non-explicit and probably very large. On the other hand, this shows that when k = d, the problem is FPT parameterized by d (or by k).

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Blocker problems
  • edge contraction
  • vertex cover
  • parameterized complexity

Metrics

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

References

  1. Hans L. Bodlaender, Pinar Heggernes, and Daniel Lokshtanov. Graph Modification Problems (Dagstuhl Seminar 14071). Dagstuhl Reports, 4(2):38-59, 2014. URL: https://doi.org/10.4230/DagRep.4.2.38.
  2. Bruno Courcelle. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  3. Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification, 2020. URL: http://arxiv.org/abs/2001.06867.
  4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  5. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. URL: https://dblp.org/rec/books/daglib/0030488.bib.
  6. Öznur Yaşar Diner, Daniël Paulusma, Christophe Picouleau, and Bernard Ries. Contraction and deletion blockers for perfect graphs and H-free graphs. Theoretical Computer Science, 746:49-72, 2018. URL: https://doi.org/10.1016/j.tcs.2018.06.023.
  7. Esther Galby, Paloma T. Lima, Felix Mann, and Bernard Ries. Using edge contractions to reduce the semitotal domination number, 2021. URL: http://arxiv.org/abs/2107.03755.
  8. Esther Galby, Paloma T. Lima, and Bernard Ries. Reducing the domination number of graphs via edge contractions and vertex deletions. Discrete Mathematics, 344(1):112169, 2021. URL: https://doi.org/10.1016/j.disc.2020.112169.
  9. Esther Galby, Felix Mann, and Bernard Ries. Blocking total dominating sets via edge contractions. Theoretical Computer Science, 877:18-35, 2021. URL: https://doi.org/10.1016/j.tcs.2021.03.028.
  10. Esther Galby, Felix Mann, and Bernard Ries. Reducing the domination number of (P₃+kP₂)-free graphs via one edge contraction. Discrete Applied Mathematics, 305:205-210, 2021. URL: https://doi.org/10.1016/j.dam.2021.09.009.
  11. Subhash Khot and Venkatesh Raman. Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science, 289(2):997-1008, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00414-5.
  12. Paloma T. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Uéverton S. Souza. Reducing graph transversals via edge contractions. Journal of Computer and System Sciences, 120:62-74, 2021. URL: https://doi.org/10.1016/j.jcss.2021.03.003.
  13. Daniël Paulusma, Christophe Picouleau, and Bernard Ries. Critical vertices and edges in H-free graphs. Discrete Applied Mathematics, 257:361-367, 2019. URL: https://doi.org/10.1016/j.dam.2018.08.016.
  14. Saket Saurabh, Uéverton dos Santos Souza, and Prafullkumar Tale. On the parameterized complexity of grid contraction. In Proc. of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 162 of LIPIcs, pages 34:1-34:17, 2020. URL: https://doi.org/10.4230/LIPIcs.SWAT.2020.34.
  15. Toshimasa Watanabe, Tadashi Ae, and Akira Nakamura. On the NP-hardness of edge-deletion and -contraction problems. Discrete Applied Mathematics, 6(1):63-78, 1983. URL: https://doi.org/10.1016/0166-218X(83)90101-4.
  16. Mihalis Yannakakis. Node- and Edge-Deletion NP-Complete Problems. In Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 253-264, 1978. URL: https://doi.org/10.1145/800133.804355.
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