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|$.