Skip to main content

Research Repository

Advanced Search

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective

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

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective Thumbnail


Authors

H.L. Bodlaender

N. Brettell

G. Paesani

E.J. van Leeuwen



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 -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 (assuming ). We also find that Edge Steiner Tree is polynomial-time solvable for -free graphs if and only if the treewidth of the class of -free graphs is bounded (subject to ). To obtain the latter result, we determine all pairs for which the class of -free graphs has bounded treewidth.

Citation

Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. (2021). Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. Theoretical Computer Science, 867, 30-39. https://doi.org/10.1016/j.tcs.2021.03.012

Journal Article Type Article
Acceptance Date Mar 4, 2021
Online Publication Date Mar 10, 2021
Publication Date May 6, 2021
Deposit Date Mar 15, 2021
Publicly Available Date Mar 28, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 867
Pages 30-39
DOI https://doi.org/10.1016/j.tcs.2021.03.012
Public URL https://durham-repository.worktribe.com/output/1245461

Files





You might also like



Downloadable Citations