Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective

Bodlaender, H.L.; 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 -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 10, 2022
• 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