TY - JOUR

T1 - Tight approximation algorithm for connectivity augmentation problems

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2008/8

Y1 - 2008/8

N2 - The S-connectivityλGS (u, v) of (u, v) in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S - {u, v} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G0 = (V, E0), S ⊆ V, and requirements r (u, v) on V × V, find a minimum size set F of new edges (any edge is allowed) so that λG0 + FS (u, v) ≥ r (u, v) for all u, v ∈ V. Extensively studied particular choices of S are the edge-CA (when S = ∅) and the node-CA (when S = V). A. Frank gave a polynomial algorithm for undirected edge-CA and observed that the directed case even with rooted{0, 1} -requirements is at least as hard as the Set-Cover problem (in rooted requirements there is s ∈ V - S so that if r (u, v) > 0 then: u = s for directed graphs, and u = s or v = s for undirected graphs). Both directed and undirected node-CA have approximation threshold Ω (2log1 - ε n). The only polylogarithmic approximation ratio known for CA was for rooted requirements-O (log n ṡ log rmax) = O (log2 n), where rmax = maxu, v ∈ V r (u, v). No nontrivial approximation algorithms were known for directed CA even for r (u, v) ∈ {0, 1}, nor for undirected CA with S arbitrary. We give an approximation algorithm for the general case that matches the known approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O (log n) for S ≠ V arbitrary, and O (rmax ṡ log n) for S = V.

AB - The S-connectivityλGS (u, v) of (u, v) in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S - {u, v} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G0 = (V, E0), S ⊆ V, and requirements r (u, v) on V × V, find a minimum size set F of new edges (any edge is allowed) so that λG0 + FS (u, v) ≥ r (u, v) for all u, v ∈ V. Extensively studied particular choices of S are the edge-CA (when S = ∅) and the node-CA (when S = V). A. Frank gave a polynomial algorithm for undirected edge-CA and observed that the directed case even with rooted{0, 1} -requirements is at least as hard as the Set-Cover problem (in rooted requirements there is s ∈ V - S so that if r (u, v) > 0 then: u = s for directed graphs, and u = s or v = s for undirected graphs). Both directed and undirected node-CA have approximation threshold Ω (2log1 - ε n). The only polylogarithmic approximation ratio known for CA was for rooted requirements-O (log n ṡ log rmax) = O (log2 n), where rmax = maxu, v ∈ V r (u, v). No nontrivial approximation algorithms were known for directed CA even for r (u, v) ∈ {0, 1}, nor for undirected CA with S arbitrary. We give an approximation algorithm for the general case that matches the known approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O (log n) for S ≠ V arbitrary, and O (rmax ṡ log n) for S = V.

KW - Approximation algorithm

KW - Connectivity augmentation

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

U2 - 10.1016/j.jcss.2007.05.002

DO - 10.1016/j.jcss.2007.05.002

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:43649084565

SN - 0022-0000

VL - 74

SP - 662

EP - 670

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 5

ER -