Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99019 (October, 1999)

An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree
by Hiroshi Nagamochi

Given a graph $G=(V,E)$ and a tree $T=(V,F)$ with $E\cap F=\emptyset$ such that $G+T=(V,F\cup E)$ is 2-edge-connected, we consider the problem of finding a smallest 2-edge-connected spanning subgraph $(V,F\cup 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.92+\epsilon)$-approximable in $O(n^{1/2}m+n^{2})$ time for any constant $\epsilon>0$, where $n=|V|$ and $m=|E\cup F|$.