# Existing results around approximation of minimum 2-edge connected Steiner subgraph

Problem $$1$$: minimum 2-edge connected subgraph

We are given a $$2$$-edge connected undirected graph $$G(V,E)$$, and we are asked to find a $$\textit{spanning}$$ subgraph $$H$$, with minimum number of edges, such that $$H$$ is $$2$$-edge connected.

There is a result by Jothi et. al. that there exists a $$\frac{5}{4}$$ approximation for the problem $$1$$.

Following is the generalized version of the problem above:

Problem $$2$$: minimum 2-edge connected Steiner subgraph

We are given a $$2$$-edge connected undirected graph $$G(V,E)$$, and a subset of vertices $$T\subseteq V$$, and we are asked to find a subgraph $$H$$, with minimum number of edges, such that $$H$$ is $$2$$-edge connected and $$T \in H$$ (ie. $$H$$ may not contain some (or all) vertices from $$V \backslash T$$).

Are there any results around approximability (or in-approximability) for the problem $$2$$, for general graphs? On searching online most of the papers I came across either talk about "descriptions" of the related polytope or approximation schemes when graphs are restricted to special classes eg planar graphs, etc.

• Yes, your problem is a special case of the much more general problem called the Survivable Network Design Problem (SNDP). It admits a 2-approximation. See books on approximation by Vazirani (Chapter 23) and Williamson-Shmoys (Chapter 11). Mar 1 at 21:47