@inproceedings{3afb9c5beb3446a1a4892deac8de794a,
title = "A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K4-Minor",
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",
author = "Carla Groenland and Jesper Nederlof and Tomohiro Koana",
note = "Publisher Copyright: {\textcopyright} Carla Groenland, Jesper Nederlof, and Tomohiro Koana.; 19th International Symposium on Parameterized and Exact Computation, IPEC 2024 ; Conference date: 04-09-2024 Through 06-09-2024",
year = "2024",
month = dec,
day = "5",
doi = "10.4230/LIPIcs.IPEC.2024.12",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Dagstuhl Publishing",
editor = "Edouard Bonnet and Pawel Rzazewski",
booktitle = "19th International Symposium on Parameterized and Exact Computation, IPEC 2024",
}