A 4/3-approximation for the minimum 2-local-vertex-connectivity augmentation in a connected graph

Given a simple connected graph G=(V,E) and a set R of pairs of vertices, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F remains simple and has at least two internally disjoint paths between u and v for each pair (u,v)∈R. The problem is known to be NP-hard, and a 3/2-approximation algorithm has been obtained so far. In this paper, we introduce new stronger lower bounds on the optimal value, and propose an O(|E|+|R|) time 4/3-approximation algorithm to the problem.