Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem

We study STEINER FOREST on H-subgraph-free graphs, that is, graphs that do not contain some fixed graph H as a (not necessarily induced) subgraph. We are motivated by a recent framework that completely characterizes the complexity of many problems on H-subgraph-free graphs. However, in contrast to, e.g. the related STEINER TREE problem, STEINER FOREST falls outside this framework. Hence, the complexity of STEINER FOREST on H-subgraph-free graphs remained tantalizingly open. We make significant progress on this open problem: our main results are four novel polynomial-time algorithms for different excluded graphs H that are central to further understand its complexity. Along the way, we study the complexity of STEINER FOREST for graphs with a small c-deletion set, that is, a small set X of vertices such that each component of G - X has size at most c. Using this parameter, we give two algorithms that we later employ as subroutines. First, we present a significantly faster parameterized algorithm for STEINER FOREST parameterized by vertical bar X vertical bar when c = 1 (i.e. the vertex cover number), which by a recent result is best possible under ETH [Feldmann and Lampis, arXiv 2024]. Second, we prove that STEINER FOREST is polynomial-time solvable for graphs with a 2-deletion set of size at most 2. The latter result is tight, as the problem is NP-complete for graphs with a 3-deletion set of size 2.