BICONNECTIVITY APPROXIMATIONS AND GRAPH CARVINGS

A spanning tree in a graph is the smallest connected spanning subgraph . Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edg e and vertex connectivity, if not specified)? Unfortunately, the probl em is known to be NP-hard. We consider the problem of finding a better approximation to the smallest 2-connected subgraph, by an efficient a lgorithm. For 2-edge connectivity, our algorithm guarantees a solution that is no more than 3/2 times the optimal. For 2-vertex connectivity , our algorithm guarantees a solution that is no more than 5/3 times t he optimal. The previous best approximation factor is 2 for each of th ese problems. The new algorithms (and their analyses) depend upon a st ructure called a carving of a graph, which is of independent interest. We show that approximating the optimal Solution to within an additive constant is NP-hard as well. We also consider the case where the grap h has edge weights. For this case, we show that an approximation facto r of 2 is possible in polynomial time for finding a k-edge connected s panning subgraph. This improves an approximation factor of 3 for k = 2 . due to Frederickson and JaJa [1981], and extends it for any k (with an increased running time though).