TY - GEN

T1 - A graph reduction step preserving element-connectivity and applications

AU - Chekuri, Chandra

AU - Korula, Nitish

N1 - Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - Given an undirected graph G=(V,E) and subset of terminals T⊆V, the element-connectivity κ́ G (u,v) of two terminals u,v T is the maximum number of u-v paths that are pairwise disjoint in both edges and non-terminals V\T (the paths need not be disjoint in terminals). Element-connectivity is more general than edge-connectivity and less general than vertex-connectivity. Hind and Oellermann [18] gave a graph reduction step that preserves the global element-connectivity of the graph. We show that this step also preserves local connectivity, that is, all the pairwise element-connectivities of the terminals. We give two applications of the step to connectivity and network design problems: First, we show a polylogarithmic approximation for the problem of packing element-disjoint Steiner forests in general graphs, and an O(1)-approximation in planar graphs. Second, we find a very short and intuitive proof of a spider-decomposition theorem of Chuzhoy and Khanna [10] in the context of the single-sink k-vertex-connectivity problem. Our results highlight the effectiveness of the element-connectivity reduction step; we believe it will find more applications in the future.

AB - Given an undirected graph G=(V,E) and subset of terminals T⊆V, the element-connectivity κ́ G (u,v) of two terminals u,v T is the maximum number of u-v paths that are pairwise disjoint in both edges and non-terminals V\T (the paths need not be disjoint in terminals). Element-connectivity is more general than edge-connectivity and less general than vertex-connectivity. Hind and Oellermann [18] gave a graph reduction step that preserves the global element-connectivity of the graph. We show that this step also preserves local connectivity, that is, all the pairwise element-connectivities of the terminals. We give two applications of the step to connectivity and network design problems: First, we show a polylogarithmic approximation for the problem of packing element-disjoint Steiner forests in general graphs, and an O(1)-approximation in planar graphs. Second, we find a very short and intuitive proof of a spider-decomposition theorem of Chuzhoy and Khanna [10] in the context of the single-sink k-vertex-connectivity problem. Our results highlight the effectiveness of the element-connectivity reduction step; we believe it will find more applications in the future.

UR - http://www.scopus.com/inward/record.url?scp=70350612645&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350612645&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-02927-1_22

DO - 10.1007/978-3-642-02927-1_22

M3 - Conference contribution

AN - SCOPUS:70350612645

SN - 3642029264

SN - 9783642029264

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 254

EP - 265

BT - Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings

T2 - 36th International Colloquium on Automata, Languages and Programming, ICALP 2009

Y2 - 5 July 2009 through 12 July 2009

ER -