@inproceedings { ,
title = {Steiner trees for hereditary graph classes},
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.},
conference = {LATIN 2020},
doi = {10.1007/978-3-030-61792-9\_48},
isbn = {9783030617912},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {613-624},
publicationstatus = {Published},
publisher = {Springer Verlag},
url = {https://durham-repository.worktribe.com/output/1141100},
volume = {14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2021},
author = {Bodlaender, H. and Brettell, N. and Johnson, M. and Paesani, G. and Paulusma, D. and van Leeuwen, E. J.}
editor = {Kohayakawa, Y. and Miyazawa, F. K.}
}