The Steiner Forest Problem revisited

The Steiner Forest Problem (SFP for short) is a natural generalization of the classical Steiner Tree Problem. Instead of only one terminal net there is given a set of terminal nets that have to be connected by choosing edges at minimum cost. Richey and Parker [M.B. Richey, R.G. Parker, On multiple Steiner subgraph problems, Networks 16 (4) (1986) 423–438] posed the question whether SFP is hard on series-parallel graphs. We partially answer this question by showing that SFP is strongly NPNP-hard on graphs with treewidth 3. On the other hand, a quadratic time algorithm for the special case on outerplanar graphs is suggested. Since series-parallel graphs have treewidth 2 and outerplanar graphs are series-parallel, we almost close the gap between polynomially solvable and hard cases.