Approximation algorithms for node and element connectivity augmentation problems.

In connectivity augmentation problems we are given a graph G = (V , E G) and an edge set E on V, and seek a min-size edge set J ⊆ E such that G ∪ J has larger connectivity than G. In the 1-Connectivity Augmentation ( 1 -CA) problem G is connected and G ∪ J should be 2-connected. In the Leaf to Leaf 1 -CA every edge in E connects two leaves in the block-tree of G. For this version we give a simple combinatorial 5/3-approximation algorithm, improving the 1.892 approximation that applies for the general case. We will also show by a simple proof that if the Steiner Tree problem admits approximation ratio α then 1 -CA admits approximation ratio 1 + ln (4 - x) + ϵ , where x is the solution to the equation 1 + ln (4 - x) = α + (α - 1) x . For the currently best value of α = ln 4 + ϵ this gives approximation ratio 1.942. This is worse than the best known ratio 1.892, but has the advantage of using Steiner Tree approximation as a "black box". In the Element Connectivity Augmentation problem we are given a graph G = (V , E) , S ⊆ V , and connectivity requirements { r (u , v) : u , v ∈ S } . The goal is to find a min-size set J of new edges on S such that for all u , v ∈ S the graph G ∪ J contains r(u, v) uv-paths such that no two of them have an edge or a node in V \ S in common. The problem is NP-hard even when r max = max u , v ∈ S r (u , v) = 2 . We obtain approximation ratio 3/2, improving the previous best ratio 7/4. For the case of degree bounds on S we obtain the same ratio with just + 1 degree violation, which is tight, since deciding whether there exists a feasible solution is NP-hard even when r max = 2 . [ABSTRACT FROM AUTHOR]