Multiway Cut

Problem definition.

In the Multiway Cut problem we are given a graph \(G(V,E)\) and a sets of \(k\) terminals. The goal is to find minimum cost set of edges whose removal disconnects each pair of terminals.

Consider the following formulation of the problem:

\begin{eqnarray*} \mbox{minimize:} & 1/2*\sum_{e\in E} \ c_e \sum_{i \in \{1,2, ... ,k\}} |c_{s(e),i}-c_{t(e),i}|& \\ \mbox{subject to:} & & \\ & \sum_{i \in \{1,2, ... , k\}} c_{v,i} = 1 & \mbox{ for every } v \in V\\ & c_{t,i}=1 & \mbox{ if t belong to i-th terminal }\\ & c_{v,i} \in \{0,1\} & \mbox{ for every } v \in V \mbox{ for every } i \in \{1,2, ... ,k\}\\ \end{eqnarray*}

comment \( c_{v,i}=1\) iff \(v\) is in part \(i\)

Solution

We put terminals in k dimensional space, with Manhattan metric, i-th terminal in point 0, 0, 0, ... 0, 0, 1(i-th position), 0, 0, ... 0, 0. All others vertices have sum of coordinates equal to 1. We minimize sum of all edges: edge cost multiply by edge length in Manhattan metric We solve the following lp to find the location of the others vertices.

\begin{eqnarray*} \mbox{minimize:} & 1/2*\sum_{e\in E} \ c_e \sum_{i \in \{1,2, ... ,k\}} |c_{s(e),i}-c_{t(e),i}|& \\ \mbox{subject to:} & & \\ & \sum_{i \in \{1,2, ... , k\}} c_{v,i} = 1 & \mbox{ for every } v \in V\\ & c_{t,i}=1 & \mbox{ if t belong to i-th terminal }\\ \end{eqnarray*}

Then several times we:

1. randomly chose radius from each terminal,
2. put each vertex in component, correspond to the first terminal, whose ball contains that vertex.

We select cheapest solution, from all randomly chosen.

Example

#include "paal/multiway_cut/multiway_cut.hpp"

#include <boost/graph/adjacency_list.hpp>

int main() {
    // sample data
    std::vector<std::pair<int,int>> edges_p{{0,3},{1,3},
                                           {0,4},{2,4},
                                           {1,5},{2,5},
                                           {3,6},{4,6},
                                           {3,7},{5,7},
                                           {4,8},{5,8},
                                           {6,7},{6,8},{7,8}
    };
    const int vertices_num = 9;
    std::vector<int> cost_edges{100,100,100,100,100,100,10,10,10,10,10,10,1,1,1};

    std::vector<int> terminals = { 0, 1, 2 };
    boost::adjacency_list<
        boost::vecS, boost::vecS, boost::undirectedS,
        boost::property<boost::vertex_index_t, int,
                        boost::property<boost::vertex_color_t, int>>,
                    boost::property<boost::edge_weight_t, int>
                    > graph(edges_p.begin(), edges_p.end(), cost_edges.begin(), vertices_num);

    for (std::size_t i = 1; i <= terminals.size(); ++i) {
        put(boost::vertex_color, graph, terminals[i - 1], i);
    }

    //solve
    std::vector<std::pair<int,int>> vertices_parts;
    auto cost_cut = paal::multiway_cut(graph, back_inserter(vertices_parts));

    //print result
    std::cout << "cost cut: " << cost_cut << std::endl;
    std::cout << "vertices (part)" << std::endl;
    for(auto i: vertices_parts) {
        std::cout << "  " << i.first << "      ( " << i.second << " )" << std::endl;
    }
    paal::lp::glp::free_env();
}

example file is multiway_cut_example.cpp

Parameters

IN: const Graph& g

OUT: OutputIterator result The pair of vertex descriptor and id of part will be output to the result output iterator The iterator type must be a model of Output Iterator

IN: const boost::bgl_named_params<P, T, R>& params

IN Rand && random_engine=std::default_random_engine(5426u)

Named Parameters

IN: iterations(int iterations)

IN: vertex_index_map(VertexIndexMap indexMap)

IN: weight_map(EdgeWeightMap weightMap) map contains weights of edges

IN: vertex_color(VertexColorMap colorMap)

Approximation ratio.

Expected Approximation Ratio equals 2. We choose rays many times to increase chance to get 2 approximation.

Complexity

Complexity of the algorithm is \(O(|LP|+|R|*(|E|+|V|*|K|))\) where R is number of repeats K is number of terminals, V is number of vertices E is number of edges and LP is cost of solve LP by simplex

The memory

Memory complexity of the algorithm is \(O(|LP|+|K|*(|V|+|E|))\) where K is number of terminals V is number of vertices, E is number of edges and LP is memory cost of solve LP by simplex

References

The algorithm analysis is described in [23]