An efficient algorithm to add up-links to a rooted tree to obtain a minimum cost 2-connected graph

We present an efficient algorithm to solve a special case of the following node-connectivity augmentation problem. Given a tree T = (V,E) and an additional set L ⊂ (V 2) of edges, called links, L ∩ E = ∅, each one with a rational nonnegative cost, find a minimum cost set of links F ⊆ L such that T + F is 2-connected. In general form, this problem is NP-hard. We focus on the up-link variation, where the tree T has a root, and every link is an edge from a node to its ancestor. We present a linear formulation for this problem together with a proof of integrality and an efficient combinatorial algorithm for it.