On multiple steiner subgraph problems
Michael B. Richey, Robert G. Parker · Networks · 1986
Abstract Recently, much attention has been given to the solvability of (otherwise intractable) combinatorial optimization problems when instances are confined to series‐parallel graphs. Substantially less is known, however, regarding those that remain hard on these particularly sparse structures. While a few ad hoc cases have been shown to be difficult, little appears to be known in terms of more generic settings. In this paper, we contend with this state of affairs by establishing that a class of Steiner subgraph‐like problems are NP‐complete on series‐parallel graphs while remaining easy (even trivial) on trees.