Pruning 2-Connected Graphs

Chandra Chekuri & Nitish Korula
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...