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 \subseteq E\) such that \(G \cup J\) has larger connectivity than G. In the 1-Connectivity Augmentation ( \(1\) -CA) problem G is connected and \(G \cup 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 \(\alpha \) then \(1\) -CA admits approximation ratio \(1+\ln (4-x)+\epsilon \) , where x is the solution to the equation \(1+\ln (4-x)=\alpha +(\alpha -1)x\) . For the currently best value of \(\alpha =\ln 4+\epsilon \) 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 \subseteq V\) , and connectivity requirements \(\{r(u,v):u,v \in S\}\) . The goal is to find a min-size set J of new edges on S such that for all \(u,v \in S\) the graph \(G \cup J\) contains r(u, v) uv-paths such that no two of them have an edge or a node in \(V \setminus S\) in common. The problem is NP-hard even when \(\displaystyle r_{\max } = \max _{u,v \in 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\) .
