Biconnectivity Approximations and Graph Carvings

Samir Khuller, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

144 Scopus citations

Abstract

A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest 1994 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 a better 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. For this case, we show that an approximation factor of 2 is possible in polynomial time for finding a k-edge connected spanning subgraph. This improves an approximation factor of 3 for k = 2, due to Frederickson and Ja´Ja´ [1981], and extends it for any k (with an increased running time though).

Original languageEnglish (US)
Pages (from-to)214-235
Number of pages22
JournalJournal of the ACM (JACM)
Volume41
Issue number2
DOIs
StatePublished - Jan 3 1994

Keywords

  • Biconnectivity
  • connectivity
  • sparse subgraphs

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Biconnectivity Approximations and Graph Carvings'. Together they form a unique fingerprint.

Cite this