{"id":"arxiv/2602.21859","url":"https://arxiv.org/abs/2602.21859","tags":["math.CO","cs.CC","cs.DM","cs.DS"],"score":0,"title":"Steiner Forest for $H$-Subgraph-Free Graphs","domain":"math.CO","source":"arxiv","authors":["Tala Eagling-Vose","David C. Kutner","Felicia Lucke","Dániel Marx","Barnaby Martin","Daniël Paulusma","Erik Jan van Leeuwen"],"reviews":0,"subject":"math.CO","summary":"Our main result is a full classification, for every connected graph $H$, of the computational complexity of Steiner Forest on $H$-subgraph-free graphs. To obtain this dichotomy, we establish the following new algorithmic, hardness, and combinatorial results: Algorithms: We identify two new classes of graph-theoretical structures that make it possible to solve Steiner Forest in polynomial time. Roughly speaking, our algorithms handle the following cases: (1) a set $X$ of vertices of bounded size that are pairwise connected by subgraphs of treewidth $2$ or bounded size, possibly together with…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-25","reactions":{}}