On the minimum local-vertex-connectivity augmentation in graphs Original Research Article

Given a graph G and target values r(u,v) prescribed for each pair of vertices u and v, we consider the problem of augmenting G by a smallest set F of new edges such that the resulting graph G+F has at least r(u,v) internally disjoint paths between each pair of vertices u and v. We show that the problem is NP-hard even if for some constant k⩾2 G is (k−1)-vertex-connected and r(u,v)∈{0,k} holds for u,v∈V. We then give a linear time algorithm which delivers a 32-approximation solution to the problem with a connected graph G and r(u,v)∈{0,2}, u,v∈V.