Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

Given a 2-edge-connected, real weighted graph $G$ with $n$ vertices and $m$ edges, the 2-edge-connectivity augmentation problem is that of finding a minimum weight set of edges of $G$ to be added to a spanning subgraph $H$ of $G$ to make it 2-edge-connected. While the general problem is NP-hard and $2$-approximable, in this paper we prove that it becomes polynomial time solvable if $H$ is a depth-first search tree of $G$. More precisely, we provide an efficient algorithm for solving this special case which runs in ${\cal O}\big(M \cdot \alpha(M,n)\big)$ time, where $\alpha$ is the classic inverse of the Ackermann's function and $M=m \cdot \alpha(m,n)$. This algorithm has two main consequences: first, it provides a faster $2$-approximation algorithm for the general $2$-edge-connectivity augmentation problem; second, it solves in ${\cal O}(m \cdot \alpha(m,n))$ time the problem of restoring, by means of a minimum weight set of replacement edges, the $2$-edge-connectivity of a 2-edge-connected communication network undergoing a link failure.