Tree Augmentation

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

#include <boost/graph/adjacency_list.hpp>

#include <iostream>

#include <vector>

int main() {

using EdgeProp = boost::property<boost::edge_weight_t, double,

boost::property<boost::edge_color_t, bool>>;

using Graph = boost::adjacency_list<boost::vecS, boost::vecS,

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

auto result = paal::ir::tree_augmentation_iterative_rounding(

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

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.

Generated on Tue Jan 31 2017 00:30:52 by 1.8.5