In this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph $G$. This problem is known to be APX-hard, both for the edge- and for the vertex-connectivity case. Here we prove that the APX-hardness still holds even if one restricts the edge costs to an interval $[1, 1+\epsilon]$, for an arbitrary small $\epsilon > 0$. This result implies the first explicit lower bound on the approximability of the general problems. On the other hand, if the input graph satisfies the sharpened $\beta$-triangle inequality, then a $\left(\frac{2}{3}+\frac{1}{3} \cdot \frac{\beta}{1-\beta}\right)$-approximation algorithm is designed. This ratio tends to $1$ with $\beta$ tending to $\frac{1}{2}$, and it improves the previous known bound of $\frac{3}{2}$, holding for graphs satisfying the triangle inequality, as soon as $\beta < \frac{5}{7}$. Furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of $G$ by means of a set of edges of minimum cost is considered. This problem is known to admit a 2-approximation algorithm. Here we show that whenever the input graph satisfies the sharpened $\beta$-triangle inequality with $\beta < \frac{2}{3}$, then this ratio can be improved to $\frac{\beta}{1-\beta}$.
On the Hardness of Constructing Minimal Biconnected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality
Proietti G;
2002
Abstract
In this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph $G$. This problem is known to be APX-hard, both for the edge- and for the vertex-connectivity case. Here we prove that the APX-hardness still holds even if one restricts the edge costs to an interval $[1, 1+\epsilon]$, for an arbitrary small $\epsilon > 0$. This result implies the first explicit lower bound on the approximability of the general problems. On the other hand, if the input graph satisfies the sharpened $\beta$-triangle inequality, then a $\left(\frac{2}{3}+\frac{1}{3} \cdot \frac{\beta}{1-\beta}\right)$-approximation algorithm is designed. This ratio tends to $1$ with $\beta$ tending to $\frac{1}{2}$, and it improves the previous known bound of $\frac{3}{2}$, holding for graphs satisfying the triangle inequality, as soon as $\beta < \frac{5}{7}$. Furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of $G$ by means of a set of edges of minimum cost is considered. This problem is known to admit a 2-approximation algorithm. Here we show that whenever the input graph satisfies the sharpened $\beta$-triangle inequality with $\beta < \frac{2}{3}$, then this ratio can be improved to $\frac{\beta}{1-\beta}$.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
