The Tree Augmentation problem is the following: given a 2-edge-connected graph \(G=(V,T\cup E)\), in which a spanning tree \(T\) is specified. The edges of this tree are called tree edges, or simply edges, while non-tree edges are called links. Links have associated nonnegative costs \(c:E\to {R}_+\). The target is to find a minimum cost subset of links that together with the tree edges give a 2-edge-connected subgraph. The problem is NP-complete, the best known approximation algorithms have factor 2.
An Integer Programming formulation of the problem is as follows. We introduce a binary variable \(x_e\) for every link \(e\). For a tree edge \(t\), let \(\delta_E(t)\) denote the set of links that connect the 2 components of the graph \((V,T-t)\). Also, let \(x(A) = \sum_{e\in A} x_e\).
\begin{eqnarray*} \mbox{minimize:} & \sum_{e\in E} \ c_e x_e & \\ \mbox{subject to:} & & \\ & x(\delta_E(t))\ge 1 & \mbox{ for every } t\in T\\ & x_e \in \{0,1\} & \mbox{ for every }e\in E\\ \end{eqnarray*}
The Tree Augmentation problem is a special case of the Steiner Network Problem. The solution presented here is the iterative rounding 2-approximation algorithm by Jain [8]. The main characteristic of this special case is that the LP relaxation that we use has polynomial size: we use the following natural relaxation of the above formulation.
\begin{eqnarray*} \mbox{minimize:} & \sum_{e\in E} \ c_e x_e & \\ \mbox{subject to:} & & \\ & x(\delta_E(t))\ge 1 & \mbox{ for every } t\in T\\ & 0 \le x_e & \mbox{ for every }e\in E\\ \end{eqnarray*}
complete example of the usage can be found in file tree_augmentation_example.cpp
The approximation ratio of this algorithm equals 2.
The time complexity of the algorithm is \(O(|T|*(|T|+|E|+LP_{time}(|E|,|T|)))\), where \(|T|\) and \(|E|\) are respectively the numbers of tree edges and links and \(LP_{time}(col, row)\) is the time of solving the LP with \(O(col)\) columns and \(O(row)\) rows.
The memory complexity of the algorithm is \(O(|E|+|T|+LP_{mem}(|E|,|T|))\), where \(LP_{mem}(col, row)\) is the memory complexity of solving the LP with \(O(col)\) columns and \(O(row)\) rows.
Jain's iterative rounding 2-approximation algorithm is described in [8]. The book [12] contains a nice description of this algorithm (Chapter 10), along with many other iterative algorithms. However, these references do not detail the Tree Augmentation Problem separately.