The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V,E) and an upper bound a(v;G) Z+{} on vertex-degree increase for each v V, find a smallest set E′ of edges such that (V,E E′) has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each v V by the addition of E′ to G is at most a(v;G), where Z+ is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(|V|+|E|) time.

The 2-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, 2VCA-SV-DC, is defined as follows: "Given an undirected graph G = (V,E), a specified set of vertices S ⊆V with |S|3 and a function g:V→Z+∪{∞}, find a smallest set E' of edges such that (V,E ∪E') has at least two internally-disjoint paths between any pair of vertices in S and such that vertex-degree increase of each v ∈V by the addition of E' to G is at most g(v), where Z+ is the set of nonnegative integers." This paper shows a linear time algorithm for 2VCA-SV-DC.