Document Open Access Logo

Reducing Graph Transversals via Edge Contractions

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2020.64.pdf
  • Filesize: 0.83 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • blocker problem
  • edge contraction
  • graph transversal
  • parameterized complexity
  • vertex cover
  • feedback vertex set
  • odd cycle transversal

Metrics

Abstract

For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection ℋ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ℋ, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.

Cite As Get BibTex

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Uéverton S. Souza. Reducing Graph Transversals via Edge Contractions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.64

Author Details

Paloma T. Lima
  • Department of Informatics, University of Bergen, Norway
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, France
Uéverton S. Souza
  • Instituto de Computação, Universidade Federal Fluminense, Niterói, Brazil

Funding

  • dos Santos, Vinicius F.: Grant APQ-02592-16 Minas Gerais Research Support Foundation (FAPEMIG) and Grants 311679/2018-8 and 421660/2016-3 National Council for Scientific and Technological Development (CNPq).
  • Sau, Ignasi: CAPES-PRINT Institutional Internationalization Program, process 88887.371209/ 2019-00, and projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).
  • Souza, Uéverton S.: Grant E-26/203.272/2017 Rio de Janeiro Research Support Foundation (FAPERJ) and Grant 303726/2017-2 National Council for Scientific and Technological Development (CNPq).

Acknowledgements

We would like to thank the anonymous reviewers for helpful remarks that improved the presentation of the manuscript.

References

  1. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, 1991. URL: https://doi.org/10.1016/0196-6774(91)90006-K.
  2. Cristina Bazgan, Cédric Bentz, Christophe Picouleau, and Bernard Ries. Blockers for the stability number and the chromatic number. Graphs and Combinatorics, 31(1):73-90, 2015. URL: https://doi.org/10.1007/s00373-013-1380-2.
  3. Cristina Bazgan, Sonia Toubaline, and Zsolt Tuza. The most vital nodes with respect to independent set and vertex cover. Discrete Applied Mathematics, 159:1933-1946, October 2011. URL: https://doi.org/10.1016/j.dam.2011.06.023.
  4. Cédric Bentz, Costa Marie-Christine, Dominique de Werra, Christophe Picouleau, and Bernard Ries. Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid. Discrete Mathematics, 310:132-146, January 2010. URL: https://doi.org/10.1016/j.disc.2009.08.009.
  5. 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.
  6. Béla Bollobás, Paul A. Catlin, and Paul Erdős. Hadwiger’s Conjecture is True for Almost Every Graph. European Journal of Combinatorics, 1(3):195-199, 1980. URL: https://doi.org/10.1016/S0195-6698(80)80001-1.
  7. Márcia R. Cerioli, Cristina G. Fernandes, Renzo Gómez, Juan Gutiérrez, and Paloma T. Lima. Transversals of longest paths. Discrete Mathematics, 343(3):111717, 2020. URL: https://doi.org/10.1016/j.disc.2019.111717.
  8. Márcia R. Cerioli and Paloma T. Lima. Intersection of longest paths in graph classes. Discrete Applied Mathematics, 2019. URL: https://doi.org/10.1016/j.dam.2019.03.022.
  9. Guantao Chen, Julia Ehrenmüller, Cristina G. Fernandes, Carl Georg Heise, Songling Shan, Ping Yang, and Amy N. Yates. Nonempty intersection of longest paths in series–parallel graphs. Discrete Mathematics, 340(3):287-304, 2017. URL: https://doi.org/10.1016/j.disc.2016.07.023.
  10. Marie-Christine Costa, Dominique de Werra, and Christophe Picouleau. Minimum d-blockers and d-transversals in graphs. Journal of Combinatorial Optimization, 22(4):857-872, 2011. URL: https://doi.org/10.1007/s10878-010-9334-6.
  11. 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.
  12. 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.
  13. 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.
  14. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. Information and Computation, 256:62-82, 2017. URL: https://doi.org/10.1016/j.ic.2017.04.009.
  15. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. URL: https://dblp.org/rec/books/daglib/0030488.bib.
  16. Ö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.
  17. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  18. Bruno Escoffier, Laurent Gourvès, and Jérôme Monnot. Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. Journal of Discrete Algorithms, 8(1):36-49, 2010. URL: https://doi.org/10.1016/j.jda.2009.01.005.
  19. Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of hadwiger number and related contraction problems: Tight lower bounds, 2020. URL: http://arxiv.org/abs/2004.11621.
  20. Fedor V. Fomin, Saket Saurabh, and Neeldhara Misra. Graph modification problems: A modern perspective. In Proc. of the 9th International Frontiers in Algorithmics Workshop (FAW), volume 9130 of LNCS, pages 3-6, 2015. URL: https://doi.org/10.1007/978-3-319-19647-3_1.
  21. Esther Galby, Paloma T. Lima, and Bernard Ries. Blocking dominating sets for H-free graphs via edge contractions. In Proc. of the 30th International Symposium on Algorithms and Computation (ISAAC), volume 149 of LIPIcs, pages 24:1-24:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.21.
  22. Esther Galby, Paloma T. Lima, and Bernard Ries. Reducing the domination number of graphs via edge contractions. In Proc. of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 138 of LIPIcs, pages 41:1-41:13, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.41.
  23. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. URL: https://dblp.org/rec/books/fm/GareyJ79.bib.
  24. Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, and Christophe Paul. Hadwiger number of graphs with small chordality. SIAM Journal on Discrete Mathematics, 29(3):1427-1451, 2015. URL: https://doi.org/10.1137/140975279.
  25. Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, and Christophe Paul. Contracting graphs to paths and trees. Algorithmica, 68(1):109-132, 2014. URL: https://doi.org/10.1007/s00453-012-9670-2.
  26. Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, and Christophe Paul. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics, 27(4):2143-2156, 2013. URL: https://doi.org/10.1137/130907392.
  27. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  28. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  29. Ramaswamy Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale. Lossy kernels for graph contraction problems. In Proc. of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 65 of LIPIcs, pages 23:1-23:14, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.23.
  30. John M. Lewis and Mihalis Yannakakis. The Node-Deletion Problem for Hereditary Properties is NP-Complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
  31. Foad Mahdavi Pajouh, Vladimir Boginski, and Eduardo Pasiliao. Minimum vertex blocker clique problem. Networks, 64:48-64, August 2014. URL: https://doi.org/10.1002/net.21556.
  32. 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.
  33. Dieter Rautenbach and Jean-Sébastien Sereni. Transversals of longest paths and cycles. SIAM Journal on Discrete Mathematics, 28(1):335-341, 2014. URL: https://doi.org/10.1137/130910658.
  34. Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  35. 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.
  36. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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