TY - CHAP

T1 - Approximating rooted connectivity augmentation problems

AU - Nutov, Zeev

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

PY - 2003

Y1 - 2003

N2 - A graph is called ℓ-connected from U tor if there are ℓ internally disjoint paths from every node u ∈ U to r. The Rooted Subset Connectivity Augmentation Problem (RSCAP) is as follows: given a graph G = (V + r, E), a node subset U ⊆ V, and an integer k, find a smallest set F of new edges such that G + F is k-connected from U to r. In this paper we consider mainly a restricted version of RSCAP in which the input graph G is already (k - 1)-connected from U to r. For this version we give an O(ln |U|)-approximation algorithm, and show that the problem cannot achieve a better approximation guarantee than the Set Cover Problem (SCP) on |U| elements and with |V| - |U| sets. For the general version of RSCAP we give an O(ln k ln |U|)-approximation algorithm. For U = V we get the Rooted Connectivity Augmentation Problem (RCAP). For directed graphs RCAP is polynomially solvable, but for undirected graphs its complexity status is not known: no polynomial algorithm is known, and it is also not known to be NP-hard. For undirected graphs with the input graph G being (k - 1)-connected from V to r, we give an algorithm that computes a solution of size exceeding a lower bound of the optimum by at most (k - 1)/2 edges.

AB - A graph is called ℓ-connected from U tor if there are ℓ internally disjoint paths from every node u ∈ U to r. The Rooted Subset Connectivity Augmentation Problem (RSCAP) is as follows: given a graph G = (V + r, E), a node subset U ⊆ V, and an integer k, find a smallest set F of new edges such that G + F is k-connected from U to r. In this paper we consider mainly a restricted version of RSCAP in which the input graph G is already (k - 1)-connected from U to r. For this version we give an O(ln |U|)-approximation algorithm, and show that the problem cannot achieve a better approximation guarantee than the Set Cover Problem (SCP) on |U| elements and with |V| - |U| sets. For the general version of RSCAP we give an O(ln k ln |U|)-approximation algorithm. For U = V we get the Rooted Connectivity Augmentation Problem (RCAP). For directed graphs RCAP is polynomially solvable, but for undirected graphs its complexity status is not known: no polynomial algorithm is known, and it is also not known to be NP-hard. For undirected graphs with the input graph G being (k - 1)-connected from V to r, we give an algorithm that computes a solution of size exceeding a lower bound of the optimum by at most (k - 1)/2 edges.

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

U2 - 10.1007/978-3-540-45198-3_13

DO - 10.1007/978-3-540-45198-3_13

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.chapter???

AN - SCOPUS:35248878568

SN - 3540407707

SN - 9783540407706

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

SP - 141

EP - 152

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

A2 - Asora, Sanjeev

A2 - Sahai, Amit

A2 - Jansen, Klaus

A2 - Rolim, Jose D.P.

PB - Springer Verlag

ER -