Tree Augmentation

# Problem definition.

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*}

# Solution

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*}

# Example

#include <iostream>
#include <vector>
int main() {
using EdgeProp = boost::property<boost::edge_weight_t, double,
boost::property<boost::edge_color_t, bool>>;
boost::undirectedS, boost::no_property, EdgeProp>;
using Edge = boost::graph_traits<Graph>::edge_descriptor;
// sample problem
std::vector<std::pair<int, int>> edges {{0,1},{1,2},{1,3},{3,4},{3,5},
{0,3},{0,3},{2,4},{2,5},{4,5}};
std::vector<EdgeProp> edge_properties {EdgeProp(0, true),
EdgeProp(0, true), EdgeProp(0, true), EdgeProp(0, true),
EdgeProp(0, true), EdgeProp(1, false), EdgeProp(1, false),
EdgeProp(1, false), EdgeProp(1, false), EdgeProp(1,false)};
Graph g(edges.begin(), edges.end(), edge_properties.begin(), 6);
std::vector<Edge> solution;
// optional input validity checking
auto tree_aug = paal::ir::make_tree_aug(g, std::back_inserter(solution));
auto error = tree_aug.check_input_validity();
if (error) {
std::cerr << "The input is not valid!" << std::endl;
std::cerr << *error << std::endl;
return -1;
}
// solve it
g, std::back_inserter(solution));
// print result
if (result.first == paal::lp::OPTIMAL) {
std::cout << "The solution contains the following nontree edges:"
<< std::endl;
for (auto e : solution) {
std::cout << "Edge " << e << std::endl;
}
std::cout << "Cost of the solution: " << *(result.second) << std::endl;
} else {
std::cout << "The instance is infeasible" << std::endl;
}
paal::lp::glp::free_env();
return 0;
}

complete example of the usage can be found in file tree_augmentation_example.cpp

# Approximation Ratio

The approximation ratio of this algorithm equals 2.

# Complexity

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.

# References

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.