Skip to main content

Research Repository

Advanced Search

Steiner trees for hereditary graph classes

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

Steiner trees for hereditary graph classes Thumbnail


Authors

H. Bodlaender

N. Brettell

G. Paesani

E. J. van Leeuwen



Contributors

Y. Kohayakawa
Editor

F. K. Miyazawa
Editor

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. (2021). Steiner trees for hereditary graph classes. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (613-624). https://doi.org/10.1007/978-3-030-61792-9_48

Conference Name LATIN 2020
Conference Location São Paulo
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 Mar 28, 2024
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

Files





You might also like



Downloadable Citations