Steiner \(k\)-edge connected subgraph polyhedra (Q1977866)

In a given graph \(G=(V,E)\) with weights \(w_e\) the Steiner \(k\)-edge survivable network problem \((\text{S}k \text{ESNP})\) is the problem of finding a minimum weight subgraph of \(G\) containing a given set \(S\subseteq V\) of nodes such that every pair of nodes in \(S\) is connected by at least \(k\) edge-disjoint paths. S\(k\)ESNP is known to be NP-hard. The authors take a polyhedral approach to tackle this problem. They show that its polytope is completely described by the trivial constraints \(0\leq x(e)\leq 1\) and the Steiner-cut constraints \(x(\delta(w)) \geq k\) if the graph \(G\) is series-parallel and if \(k\) is even. The resulting linear description yields polynomial-time algorithms for solving this special case of S\(k\)ESNP.