Abstract:
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.