A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor

Carla Groenland, Jesper Nederlof, Tomohiro Koana

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 termi…