A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K4-Minor
Publication date
2024-12-05
Authors
Groenland, Carla
Nederlof, Jesper
Koana, Tomohiro
Editors
Bonnet, Edouard
Rzazewski, Pawel
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
Abstract
We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in O(n4) time, where n denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time.
Keywords
rooted minor, Steiner tree, Software
Citation
Groenland, C, Nederlof, J & Koana, T 2024, A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K 4 -Minor. in E Bonnet & P Rzazewski (eds), 19th International Symposium on Parameterized and Exact Computation, IPEC 2024., 12, Leibniz International Proceedings in Informatics, LIPIcs, vol. 321, Dagstuhl Publishing, 19th International Symposium on Parameterized and Exact Computation, IPEC 2024, London, United Kingdom, 4/09/24. https://doi.org/10.4230/LIPIcs.IPEC.2024.12, conference