Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-041 | 6th March 2006 00:00

#### k-connected spanning subgraphs of low degree

TR06-041
Authors: Tomas Feder, Rajeev Motwani, An Zhu
Publication: 21st March 2006 08:13
Keywords:

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.

ISSN 1433-8092 | Imprint
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9453086853027344, "perplexity": 2210.5059081940917}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-21/segments/1620243991252.15/warc/CC-MAIN-20210512035557-20210512065557-00171.warc.gz"}