2026-07-24T21:21:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22238 2024-12-05T15:32:41Z ddc:004 open_access

A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K₄-Minor Groenland, Carla Nederlof, Jesper Koana, Tomohiro Steiner tree rooted minor 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(n⁴) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carla Groenland and Jesper Nederlof and Tomohiro Koana 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.12 urn:nbn:de:0030-drops-222387 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.12 eng https://creativecommons.org/licenses/by/4.0/legalcode