Steiner 2-Edge Connected Subgraph Polytopes on Series-Parallel Graphs

Source abstract

Given a graph G=(V,E) with weights on its edges and a set of specified nodes $S\subseteq V$, the Steiner 2-edge survivable network problem is to find a minimum weight subgraph of G such that between every two nodes of S there are at least two edge-disjoint paths. This problem has applications to the design of reliable communication and transportation networks. In this paper, we give a complete linear description of the polytope associated with the solutions to this problem when the underlying graph is series-parallel. We also discuss related polyhedra.