Cookies

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.

Bodlaender, H. and Brettell, N. and Johnson, M. and Paesani, G. and Paulusma, D. and van Leeuwen, E.J. (2020) 'Steiner trees for hereditary graph classes.', in LATIN 2020: Theoretical Informatics. , pp. 613-624. Lecture Notes in Computer Science., 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings

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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(407Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-030-61792-9_48
Publisher statement:The final authenticated version is available online at https://doi.org/10.1007/978-3-030-61792-9_48
Date accepted:11 February 2020
Date deposited:26 April 2020
Date of first online publication:03 December 2020
Date first made open access:21 January 2021

Save or Share this output

Export:
Export
Look up in GoogleScholar