A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor
<|reference_start|>A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-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^4)$ 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.<|reference_end|>
@article{groenland2024a,
    title={A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a
  $K_4$-Minor},
    author={Carla Groenland and Jesper Nederlof and Tomohiro Koana},
    journal={arXiv preprint arXiv:2410.06793},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06793},
    primaryClass={cs.DS}
}