Document Open Access Logo

Reducing the Domination Number of Graphs via Edge Contractions

Authors Esther Galby, Paloma T. Lima, Bernard Ries

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.41.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Esther Galby
  • Department of Informatics, University of Fribourg, Fribourg, Switzerland
Paloma T. Lima
  • Department of Informatics, University of Bergen, Bergen, Norway
Bernard Ries
  • Department of Informatics, University of Fribourg, Fribourg, Switzerland

Cite As Get BibTex

Esther Galby, Paloma T. Lima, and Bernard Ries. Reducing the Domination Number of Graphs via Edge Contractions. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.41

Abstract

In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k <= 2, the problem is coNP-hard. We further prove that for k=1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and that it remains NP-hard when restricted to P_9-free graphs, bipartite graphs and {C_3,...,C_{l}}-free graphs for any l >= 3. Finally, we show that for any k >= 1, the problem is polynomial-time solvable for P_5-free graphs and that it can be solved in FPT-time and XP-time when parameterized by tree-width and mim-width, respectively.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • domination number
  • blocker problem
  • graph classes

Metrics

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

References

  1. 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.
  2. Cristina Bazgan, Sonia Toubaline, and Daniel Vanderpooten. Critical edges for the assignment problem: Complexity and exact resolution. Operations Research Letters, 41:685–689, November 2013. URL: https://doi.org/10.1016/j.orl.2013.10.001.
  3. 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.
  4. Cédric Bentz, Costa Marie-Christine, Dominique de Werra, Christophe Picouleau, and Bernard Ries. Weighted Transversals and Blockers for Some Optimization Problems in Graphs, pages 203-222. Progress in Combinatorial Optimization. ISTE-WILEY, 2012. Google Scholar
  5. Alan A. Bertossi. Dominating sets for split and bipartite graphs. Information Processing Letters, 19(1):37-40, 1984. URL: https://doi.org/10.1016/0020-0190(84)90126-1.
  6. 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.
  7. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  8. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg; New York, fourth edition, 2010. Google Scholar
  9. Öznur Yaşar Diner, Daniël Paulusma, Christophe Picouleau, and Bernard Ries. Contraction Blockers for Graphs with Forbidden Induced Paths. In Algorithms and Complexity, pages 194-207, Cham, 2015. Springer International Publishing. Google Scholar
  10. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the Tractability of Optimization Problems on H-Graphs. In ESA 2018, volume 112 of LIPIcs, pages 30:1-30:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.30.
  11. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990. Google Scholar
  12. Teresa W. Haynes, S. T. Hedetniemi, and Peter J. Slater. Fundamentals of domination in graphs. New York : Marcel Dekker, 1998. Google Scholar
  13. Jia Huang and Jun-Ming Xu. Domination and Total Domination Contraction Numbers of Graphs. Ars Combinatoria, 94, January 2010. Google Scholar
  14. Foad Mahdavi Pajouh, Vladimir Boginski, and Eduardo Pasiliao. Minimum Vertex Blocker Clique Problem. Networks, 64, August 2014. URL: https://doi.org/10.1002/net.21556.
  15. Daniël Paulusma, Christophe Picouleau, and Bernard Ries. Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions. In ISCO 2016, volume 9849 of LNCS, pages 38-49, 2016. URL: https://doi.org/10.1007/978-3-319-45587-7_4.
  16. Daniël Paulusma, Christophe Picouleau, and Bernard Ries. Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions. In TAMC 2017, volume 10185 of LNCS, pages 470-483, 2017. URL: https://doi.org/10.1007/978-3-319-55911-7_34.
  17. 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.
  18. Martin Vatshelle. New width parameters of graphs. PhD thesis, University of Bergen, Norway, 2012. Google Scholar
  19. Ö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.
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 About DROPS Imprint Privacy Contact