{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiafbnfz5zewyvi7dexubn32hx3jwj573do4apavv4kqih65up5pcm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfsmmuesmkj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.21859v1",
  "publishedAt": "2026-02-26T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Tala Eagling-Vose",
    "David C. Kutner",
    "Felicia Lucke",
    "Dániel Marx",
    "Barnaby Martin",
    "Daniël Paulusma",
    "Erik Jan van Leeuwen"
  ],
  "textContent": "**Authors:** Tala Eagling-Vose, David C. Kutner, Felicia Lucke, Dániel Marx, Barnaby Martin, Daniël Paulusma, Erik Jan van Leeuwen\n\nOur 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 an independent set of arbitrary size that is connected to $X$ in an arbitrary way; (2) a set $X$ of vertices of arbitrary size that are pairwise connected in a cyclic manner by subgraphs of treewidth $2$ or bounded size. Hardness results: We show that Steiner Forest remains NP-complete for graphs with 2-deletion set number $3$. (The $c$-deletion set number is the size of a smallest cutset $S$ such that every component of $G-S$ has at most $c$ vertices.) Combinatorial results: To establish the dichotomy, we perform a delicate graph-theoretic analysis showing that if $H$ is a path or a subdivided claw, then excluding $H$ as a subgraph either yields one of the two algorithmically favourable structures described above, or yields a graph class for which NP-completeness of Steiner Forest follows from either our new hardness result or a previously known one. Along the way to classifying the hardness for excluded subgraphs, we establish a dichotomy for graphs with $c$-deletion set number at most $k$. Specifically, our results together with pre-existing ones show that Steiner Forest is polynomial-time solvable if (1) $c=1$ and $k\\geq 0$, or (2) $c=2$ and $k\\leq 2$, or (3) $c\\geq 3$ and $k=1$, and is NP-complete otherwise.",
  "title": "Steiner Forest for $H$-Subgraph-Free Graphs"
}