TR06-041 Authors: Tomas Feder, Rajeev Motwani, An Zhu

Publication: 21st March 2006 08:13

Downloads: 1304

Keywords:

We consider the problem of finding a $k$-vertex ($k$-edge)

connected spanning subgraph $K$ of a given $n$-vertex graph $G$

while minimizing the maximum degree $d$ in $K$. We give a

polynomial time algorithm for fixed $k$ that achieves an $O(\log

n)$-approximation. The only known previous polynomial algorithms

achieved degree $d+1$ for optimum $d$ if $k=1$ (the case of

spanning trees) and a factor $O(n^{\delta})$ for any $\delta>0$ if

$k=2$ for the case of 2-edge connectivity. Our result answers open

problems of Ravi, Raghavachari, and Klein~\cite{rrk,k} and

Hochbaum~\cite{h}. The result extends to a weighted version with

non-uniform degree bounds for different vertices. Our approach is

based on an $O(\log n)$-approximation bound for a problem that

combines set cover and degree minimization, thus extending the

tight $\Theta(\log n)$ bound for set cover. We also consider

extensions to finding $k$-connected subgraphs or minors of low degree

spanning a large fraction of the vertices, for $k=1,2,3$,

with an application to finding long cycles in graphs.