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 O(M α(M,n)) time, where α is the classic inverse of Ackermann's function and M=m α(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 O(m α(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.