We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
Download PDF
Publisher Web site:
Publisher statement:© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
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