Steiner Forest for $H$-Subgraph-Free Graphs

Tala Eagling-Vose, David C. Kutner, Felicia Lucke, Dániel Marx, Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen

arXivarxiv/2602.21859Feb 25, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.21859
curl -X POST /api/v1/records/arxiv/2602.21859/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.21859/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'