Bounded-Degree Minimum Spanning Tree

Problem definition.

In the Bounded-Degree Minimum Spanning Tree problem we are given: a connected, undirected graph \(G=(V,E)\) with edge costs \(c:E\to R\) and degree upper bounds \(B_v\) for each \(v\in V\). The goal is to find a spanning tree \(T\) of minimum cost, which satisfies the degree bounds, that is: \(deg_T(v) \leq B_v\) for each \(v\in V\). Both finding the optimal spanning tree and deciding whether a spanning tree satisfying the degree bounds exists are NP-complete problems.

An Integer Programming formulation of the problem is as follows. We introduce a binary variable \(x_e\) for every edge \(e\in E\). For a vertex \(v\), let \(\delta(v)\) denote the set of edges incident with \(v\) in \(G\). For a set of vertices \(S\subseteq V\) let \(E(S)\) denote the the set of edges \(e\in E\) with both endpoints in \(S\). 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(E(V))=|V|-1 & \\ & x(E(S)) \leq |S|-1 & \mbox{ for every } \emptyset \neq S \subset V \\ & x(\delta(v))\leq B_v & \mbox{ for every } v \in V\\ & x_e \in \{0,1\} & \mbox{ for every } e\in E\\ \end{eqnarray*}

Solution

We use a natural relaxation of the above IP formulation, where we replace condition:

\begin{eqnarray*} & x_e \in \{0,1\} & \mbox{ for every } e\in E\\ \end{eqnarray*}

with:

\begin{eqnarray*} & 0 \leq x_e \leq 1 & \mbox{ for every } e\in E\\ \end{eqnarray*}

The algorithm then follows the Iterative Rounding framework:

repeat:

• find an extreme point solution to the LP
• remove all edges with \(x_e=0\) from \(G\) (round)
• remove a degree bound \(B_v\) such that \(deg_G(v) \leq B_v + 1\) from the LP (relax)

until solution to the LP is integral.

As the LP formulation has got an exponential number of constraints, we need to use a separation oracle and the row generation technique to solve it.

Example

#include "paal/iterative_rounding/bounded_degree_min_spanning_tree/bounded_degree_mst.hpp"
#include "paal/utils/functors.hpp"

#include <boost/graph/adjacency_list.hpp>

#include <iostream>
#include <vector>

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS,
        boost::undirectedS, boost::no_property,
        boost::property<boost::edge_weight_t, int>>;
    using Edge = boost::graph_traits<Graph>::edge_descriptor;

    // sample problem
    std::vector<std::pair<int, int>> edges {{0,1},{0,2},{1,2},{1,3},{1,4},
        {1,5},{5,0},{3,4}};
    std::vector<int> costs {1,2,1,2,1,1,1,5};
    std::vector<int> bounds {3,2,2,2,2,2};

    Graph g(edges.begin(), edges.end(), costs.begin(), 6);
    auto degree_bounds = paal::utils::make_array_to_functor(bounds);

    std::vector<Edge> result_tree;

    // optional input validity checking
    auto bdmst = paal::ir::make_bounded_degree_mst(
        g, degree_bounds, std::back_inserter(result_tree));
    auto error = bdmst.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::bounded_degree_mst_iterative_rounding(
        g, degree_bounds, std::back_inserter(result_tree));

    // print result
    if (result.first == paal::lp::OPTIMAL) {
        std::cout << "Edges in the spanning tree" << std::endl;
        for (auto e : result_tree) {
            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 bounded_degree_mst_example.cpp

Approximation ratio

This algorithm doesn't have an approximation ratio in classical sense, but is a bicriteria approximation: one criteria is the cost, whereas the other one is violation of the degree bounds. The solution returned by the algorithm has lower cost than the optimal one but can violate the constraints by one.

Complexity

The time complexity of the algorithm is \(O(|V|*(|V|+|E|+LP_{rowgen}))\), where \(|V|\) and \(|E|\) are respectively the numbers of vertices and edges whereas \(LP_{rowgen}\) is the time of solving the LP using row generation technique. \(LP_{rowgen}=O(rows * (|V|^4 + LP_{time}(|E|,|V|)))\), where \(rows\) is the number of generated rows 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(|V|+|E|+LP_{mem}(|E|,|V|))\), where \(LP_{mem}(col, row)\) is the memory complexity of solving the LP with \(O(col)\) columns and \(O(row)\) rows.

References

This iterative rounding additive one approximation by Singh and Lau is described in [20].