Complexity framework for forbidden subgraphs IV: The Steiner Forest problem

Abstract

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. In contrast to the related STEINER TREE problem, STEINER FOREST falls outside a recent framework that completely characterizes the complexity of many problems on H-subgraph-free graphs. Hence, the complexity of STEINER FOREST on H-subgraph-free graphs remained open. Our main results are four polynomial-time algorithms for different excluded graphs H that are central to further understand its complexity. We also 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 connected component of G−X has size at most c. For this parameter, we give two algorithms that we later employ as subroutines (including a faster algorithm when c=1, that is, the vertex cover number) and exhibit a dichotomy theorem.