Summary: Consider the following problem: given a graph with edge-weights and a subset \(Q\) of vertices, find a minimum-weight subgraph in which there are two edge-disjoint paths connecting every pair of vertices in \(Q\). The problem is a failure-resilient analog of the Steiner tree problem, and arises in telecommunications applications. A more general formulation, also employed in telecommunications optimization, assigns a number (or requirement) \(r _{v } \in \{0,1,2\}\) to each vertex \(v\) in the graph; for each pair \(u, v\) of vertices, the solution network is required to contain \(\min\{r _{u }, r _{v }\}\) edge-disjoint \(u\)-to-\(v\) paths.
We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is SNP-hard in general graphs and NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is \(O(n \log n)\).
Under the additional restriction that the requirements are in \(\{0,2\}\) for vertices on the boundary of a single face of a planar graph, we give a linear-time algorithm to find the optimal solution.
For the entire collection see [Zbl 1142.68001].