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 Leaf1-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 α=ln4+ϵ 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=maxu,v∈Sr(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.