Steiner trees for hereditary graph classes

Bodlaender, H.; Brettell, N.; Johnson, M.; Paesani, G.; Paulusma, D.; van Leeuwen, E. J.

Abstract

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H1,H2) -free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree. We also find that Edge Steiner Tree is polynomial-time solvable for (H1,H2) -free graphs if and only if the treewidth of the class of (H1,H2) -free graphs is bounded (subject to P≠NP ). To obtain the latter result, we determine all pairs (H1,H2) for which the class of (H1,H2) -free graphs has bounded treewidth.

Citation

Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2020, May). Steiner trees for hereditary graph classes. Presented at LATIN 2020, São Paulo

• Presentation Conference Type: Conference Paper (published)
• Conference Name: LATIN 2020
• Start Date: May 25, 2020
• End Date: May 29, 2020
• Acceptance Date: Feb 11, 2020
• Online Publication Date: Dec 3, 2020
• Publication Date: 2021-01
• Deposit Date: Apr 26, 2020
• Publicly Available Date: Apr 26, 2020
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Volume: 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings
• Pages: 613-624
• Series Title: Lecture Notes in Computer Science
• Book Title: LATIN 2020: Theoretical Informatics
• ISBN: 9783030617912
• DOI: https://doi.org/10.1007/978-3-030-61792-9_48
• Public URL: https://durham-repository.worktribe.com/output/1141100