Bodlaender, H.L. and Brettell, N. and Johnson, M. and Paesani, G. and Paulusma, D. and van Leeuwen, E.J. (2021) 'Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective.', Theoretical computer science., 867 . pp. 30-39.
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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
Download PDF (476Kb)
|Publisher Web site:||https://doi.org/10.1016/j.tcs.2021.03.012|
|Publisher statement:||© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||04 March 2021|
|Date deposited:||19 March 2021|
|Date of first online publication:||10 March 2021|
|Date first made open access:||10 March 2022|
Save or Share this output
|Look up in GoogleScholar|