Document Open Access Logo

Domination and Cut Problems on Chordal Graphs with Bounded Leafage

Authors Esther Galby, Dániel Marx , Philipp Schepper , Roohani Sharma , Prafullkumar Tale

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.14.pdf
  • Filesize: 0.99 MB
  • 24 pages

Document Identifiers

Author Details

Esther Galby
  • TU Hamburg, Germany
Dániel Marx
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Philipp Schepper
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Roohani Sharma
  • Max Planck Institute for Informatics, SIC, Saarbrücken, Germany
Prafullkumar Tale
  • Indian Institute of Science Education and Research, Pune, India

Funding

Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH. Esther Galby and Prafullkumar Tale: Part of the work was carried out when the authors were Post-Doctoral Researchers at CISPA Helmholtz Center for Information Security, Germany.
  • Schepper, Philipp: Part of Saarbrücken Graduate School of Computer Science, Germany.

Cite AsGet BibTex

Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale. Domination and Cut Problems on Chordal Graphs with Bounded Leafage. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.IPEC.2022.14

Abstract

The leafage of a chordal graph G is the minimum integer 𝓁 such that G can be realized as an intersection graph of subtrees of a tree with 𝓁 leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1). We present a conceptually much simpler algorithm that runs in time 2^𝒪(𝓁) ⋅ n^𝒪(1). We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple n^𝒪(𝓁)-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in n^O(1)-time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Chordal Graphs
  • Leafage
  • FPT Algorithms
  • Dominating Set
  • MultiCut with Undeletable Terminals
  • Multiway Cut with Undeletable Terminals

Metrics

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

Related Versions

References

  1. Liliana Alcón. On asteroidal sets in chordal graphs. Discret. Appl. Math., 164:482-491, 2014. URL: https://doi.org/10.1016/j.dam.2013.04.019.
  2. Vikraman Arvind, Roman Nedela, Ilia Ponomarenko, and Peter Zeman. Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable. CoRR, abs/2107.10689, 2021. URL: http://arxiv.org/abs/2107.10689.
  3. Hari Balakrishnan, Anand Rajaraman, and C. Pandu Rangan. Connected domination and steiner set on asteroidal triple-free graphs. In Frank K. H. A. Dehne, Jörg-Rüdiger Sack, Nicola Santoro, and Sue Whitesides, editors, Algorithms and Data Structures, Third Workshop, WADS '93, Montréal, Canada, August 11-13, 1993, Proceedings, volume 709 of Lecture Notes in Computer Science, pages 131-141. Springer, 1993. URL: https://doi.org/10.1007/3-540-57155-8_242.
  4. Kathleen D. Barnetson, Andrea C. Burgess, Jessica A. Enright, Jared Howell, David A. Pike, and Brady Ryan. The firebreak problem. Networks, 77(3):372-382, 2021. URL: https://doi.org/10.1002/net.21975.
  5. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token sliding on split graphs. Theory Comput. Syst., 65(4):662-686, 2021. URL: https://doi.org/10.1007/s00224-020-09967-8.
  6. Benjamin Bergougnoux and Mamadou Moustapha Kanté. More applications of the d-neighbor equivalence: Acyclicity and connectivity constraints. SIAM J. Discret. Math., 35(3):1881-1926, 2021. URL: https://doi.org/10.1137/20M1350571.
  7. Benjamin Bergougnoux, Charis Papadopoulos, and Jan Arne Telle. Node multiway cut and subset feedback vertex set on graphs of bounded mim-width. Algorithmica, 84(5):1385-1417, 2022. URL: https://doi.org/10.1007/s00453-022-00936-w.
  8. Alan A. Bertossi. Dominating sets for split and bipartite graphs. Inf. Process. Lett., 19(1):37-40, 1984. URL: https://doi.org/10.1016/0020-0190(84)90126-1.
  9. Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé. Multicut is FPT. SIAM J. Comput., 47(1):166-207, 2018. URL: https://doi.org/10.1137/140961808.
  10. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci., 511:66-76, 2013. URL: https://doi.org/10.1016/j.tcs.2013.01.009.
  11. Peter Buneman. A characterisation of rigid circuit graphs. Discret. Math., 9(3):205-212, 1974. URL: https://doi.org/10.1016/0012-365X(74)90002-8.
  12. Yixin Cao. Linear recognition of almost interval graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1096-1115. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch77.
  13. Maw-Shang Chang. Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput., 27(6):1671-1694, 1998. URL: https://doi.org/10.1137/S0097539792238431.
  14. Steven Chaplick and Juraj Stacho. The vertex leafage of chordal graphs. Discret. Appl. Math., 168:14-25, 2014. URL: https://doi.org/10.1016/j.dam.2012.12.006.
  15. Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx. Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms, 11(4):28:1-28:28, 2015. URL: https://doi.org/10.1145/2700209.
  16. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput., 42(4):1674-1696, 2013. URL: https://doi.org/10.1137/12086217X.
  17. 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.
  18. Celina M. H. de Figueiredo, Raul Lopes, Alexsander Andrade de Melo, and Ana Silva. Parameterized algorithms for steiner tree and dominating set: Bounding the leafage by the vertex leafage. In Petra Mutzel, Md. Saidur Rahman, and Slamin, editors, WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings, volume 13174 of Lecture Notes in Computer Science, pages 251-262. Springer, 2022. URL: https://doi.org/10.1007/978-3-030-96731-4_21.
  19. Pål Grønås Drange, Markus S. Dregi, and Pim van 't Hof. On the computational complexity of vertex integrity and component order connectivity. Algorithmica, 76(4):1181-1202, 2016. URL: https://doi.org/10.1007/s00453-016-0127-x.
  20. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the Tractability of Optimization Problems on H-graphs. Algorithmica, 82(9):2432-2473, 2020. URL: https://doi.org/10.1007/s00453-020-00692-9.
  21. Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger. Enumerating minimal subset feedback vertex sets. Algorithmica, 69(1):216-231, 2014. URL: https://doi.org/10.1007/s00453-012-9731-6.
  22. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399-404, 1956. URL: https://doi.org/10.4153/CJM-1956-045-5.
  23. Esther Galby, Dániel Marx, Philipp Schepper, Roohani Sharma, and Prafullkumar Tale. Domination and cut problems on chordal graphs with bounded leafage. CoRR, abs/2208.02850, 2022. URL: https://doi.org/10.48550/arXiv.2208.02850.
  24. Fanica Gavril. The intersection graphs of subtrees in tree are exactly the chordal graphs. Combinatorica, 1974. Google Scholar
  25. P. C. Gilmore and A. J. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 16:539-548, 1964. URL: https://doi.org/10.4153/CJM-1964-055-5.
  26. Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, and Christophe Paul. Hadwiger number of graphs with small chordality. SIAM J. Discret. Math., 29(3):1427-1451, 2015. URL: https://doi.org/10.1137/140975279.
  27. Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. Elsevier, 2004. Google Scholar
  28. Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, and Johannes Uhlmann. Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. Eur. J. Oper. Res., 186(2):542-553, 2008. URL: https://doi.org/10.1016/j.ejor.2007.02.014.
  29. Michel Habib and Juraj Stacho. Polynomial-time algorithm for the leafage of chordal graphs. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 290-300. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_27.
  30. Michel Habib and Juraj Stacho. Reduced clique graphs of chordal graphs. Eur. J. Comb., 33(5):712-735, 2012. URL: https://doi.org/10.1016/j.ejc.2011.09.031.
  31. Winfried Hochstättler, Johann L. Hurink, Bodo Manthey, Daniël Paulusma, Britta Peis, and Georg Still. In memoriam walter kern. Discret. Appl. Math., 303:2-3, 2021. URL: https://doi.org/10.1016/j.dam.2021.08.034.
  32. Kyriaki Ioannidou, George B. Mertzios, and Stavros D. Nikolopoulos. The longest path problem has a polynomial solution on interval graphs. Algorithmica, 61(2):320-341, 2011. URL: https://doi.org/10.1007/s00453-010-9411-3.
  33. Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. A width parameter useful for chordal and co-comparability graphs. Theor. Comput. Sci., 704:1-17, 2017. URL: https://doi.org/10.1016/j.tcs.2017.09.006.
  34. J. Mark Keil. Finding hamiltonian circuits in interval graphs. Inf. Process. Lett., 20(4):201-206, 1985. URL: https://doi.org/10.1016/0020-0190(85)90050-X.
  35. Athanasios L. Konstantinidis and Charis Papadopoulos. Cluster deletion on interval graphs and split related graphs. Algorithmica, 83(7):2018-2046, 2021. URL: https://doi.org/10.1007/s00453-021-00817-8.
  36. Dieter Kratsch. Finding the minimum bandwidth of an interval graphs. Inf. Comput., 74(2):140-158, 1987. URL: https://doi.org/10.1016/0890-5401(87)90028-9.
  37. Dieter Kratsch and Lorna Stewart. Approximating bandwidth by mixing layouts of interval graphs. SIAM J. Discret. Math., 15(4):435-449, 2002. URL: https://doi.org/10.1137/S0895480199359624.
  38. C. Lekkeikerker and J. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 51(1):45-64, 1962. URL: http://eudml.org/doc/213681.
  39. In-Jen Lin, Terry A. McKee, and Douglas B. West. The leafage of a chordal graph. Discuss. Math. Graph Theory, 18(1):23-48, 1998. URL: https://doi.org/10.7151/dmgt.1061.
  40. George S. Lueker and Kellogg S. Booth. A linear time algorithm for deciding interval graph isomorphism. J. ACM, 26(2):183-195, 1979. URL: https://doi.org/10.1145/322123.322125.
  41. Dániel Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.007.
  42. Dániel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput., 43(2):355-388, 2014. URL: https://doi.org/10.1137/110855247.
  43. Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh, and Roohani Sharma. Quick separation in chordal and split graphs. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 70:1-70:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.70.
  44. Charis Papadopoulos. Restricted vertex multicut on permutation graphs. Discret. Appl. Math., 160(12):1791-1797, 2012. URL: https://doi.org/10.1016/j.dam.2012.03.021.
  45. Charis Papadopoulos and Spyridon Tzimas. Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. Discret. Appl. Math., 258:204-221, 2019. URL: https://doi.org/10.1016/j.dam.2018.11.017.
  46. Charis Papadopoulos and Spyridon Tzimas. Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage. In Cristina Bazgan and Henning Fernau, editors, Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings, volume 13270 of Lecture Notes in Computer Science, pages 466-479. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-06678-8_34.
  47. James Richard Walter. Representations of rigid cycle graphs. Wayne State University, 1972. Google Scholar
  48. Kevin White, Martin Farber, and William R. Pulleyblank. Steiner trees, connected domination and strongly chordal graphs. Networks, 15(1):109-124, 1985. URL: https://doi.org/10.1002/net.3230150109.
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