Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

In this paper we reassess the parameterized complexity and approximability of the well-studied Steiner Forest problem in several graph classes of bounded width. The problem takes an edge-weighted graph and pairs of vertices as input, and the aim is to find a minimum cost subgraph in which each given vertex pair lies in the same connected component. It is known that this problem is APX-hard in general, and NP-hard on graphs of treewidth 3, treedepth 4, and feedback vertex set size 2. However, Bateni, Hajiaghayi and Marx JACM, 2011 gave an approximation scheme with a runtime of n^O (k²{) } on graphs of treewidth k. Our main result is a much faster efficient parameterized approximation scheme (EPAS) with a runtime of 2^O (k²{ k²) } n^O (1). If k instead is the vertex cover number of the input graph, we show how to compute the optimum solution in 2^O (k k) n^O (1) time, and we also prove that this runtime dependence on k is asymptotically best possible, under ETH. Furthermore, if k is the size of a feedback edge set, then we obtain a faster 2^O (k) n^O (1) time algorithm, which again cannot be improved under ETH.