An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree Original Research Article

Given a graph G=(V,E) and a tree T=(V,F) with E∩F=∅ such that G+T=(V,F∪E) is 2-edge-connected, we consider the problem of finding a smallest 2-edge-connected spanning subgraph (V,F∪E′) of G+T containing T. The problem, which is known to be NP-hard, admits a 2-approximation algorithm. However, obtaining a factor better than 2 for this problem has been one of the main open problems in the graph augmentation problem. In this paper, we show that the problem is (1.875+ε)-approximable in O(n1/2m+n2) time for any constant ε>0, where n=|V| and m=|E∪F|.