2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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). $\endgroup$ Mar 1 at 21:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.