TY - GEN

T1 - Biconnectivity approximations and graph carvings

AU - Khuller, Samir

AU - Vishkin, Uzi

N1 - Funding Information:
“Partially supported by NSF grants CCR-890S949, CCR- 9103135 and CCR-9111348. Institute for Advanced Computer Studies (UMIACS), University of Maryland, College Park, MD 20742.
Publisher Copyright:
© 1992 ACM.

PY - 1992/7/1

Y1 - 1992/7/1

N2 - 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 edge and vertex connectivity, if not specified) ? Unfortunately, the problem is known to be NP-hard. We consider the problem of finding an approximation to the smallest 2-connected subgraph, by an efficient algorithm. 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 the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure 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 graph has edge weights. We show that an approximation factor of 2 is possible in polynomial time for finding a κ-edge connected spanning subgraph. This improves an approximation factor of 3 for κ = 2 due to [FJ81], and extends it for any κ (with an increased running time though).

AB - 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 edge and vertex connectivity, if not specified) ? Unfortunately, the problem is known to be NP-hard. We consider the problem of finding an approximation to the smallest 2-connected subgraph, by an efficient algorithm. 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 the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure 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 graph has edge weights. We show that an approximation factor of 2 is possible in polynomial time for finding a κ-edge connected spanning subgraph. This improves an approximation factor of 3 for κ = 2 due to [FJ81], and extends it for any κ (with an increased running time though).

UR - http://www.scopus.com/inward/record.url?scp=0027004052&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027004052&partnerID=8YFLogxK

U2 - 10.1145/129712.129786

DO - 10.1145/129712.129786

M3 - Conference contribution

AN - SCOPUS:0027004052

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 759

EP - 770

BT - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992

PB - Association for Computing Machinery

T2 - 24th Annual ACM Symposium on Theory of Computing, STOC 1992

Y2 - 4 May 1992 through 6 May 1992

ER -