2026-08-12T12:57:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1746 2024-03-06T10:33:06Z ddc:004 open_access

Pruning 2-Connected Graphs Chekuri, Chandra Korula, Nitish 2-Connected Graphs k-MST Density Approximation Given an edge-weighted undirected graph $G$ with a specified set of terminals, let the \emph{density} of any subgraph be the ratio of its weight/cost to the number of terminals it contains. If $G$ is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of $G$? We answer this question in the affirmative by giving an algorithm to \emph{prune} $G$ and find such subgraphs of any desired size, at the cost of only a logarithmic increase in density (plus a small additive factor). We apply the pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the \kv problem, we are given an undirected graph $G$ with edge costs and an integer $k$; the goal is to find a minimum-cost 2-vertex-connected subgraph of $G$ containing at least $k$ vertices. In the \bv\ problem, we are given the graph $G$ with edge costs, and a budget $B$; the goal is to find a 2-vertex-connected subgraph $H$ of $G$ with total edge cost at most $B$ that maximizes the number of vertices in $H$. We describe an $O(\log n \log k)$ approximation for the \kv problem, and a bicriteria approximation for the \bv\ problem that gives an $O(\frac{1}{\eps}\log^2 n)$ approximation, while violating the budget by a factor of at most $3+\eps$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chandra Chekuri and Nitish Korula 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1746 urn:nbn:de:0030-drops-17469 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1746 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode