All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
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\)


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.


#include <boost/graph/adjacency_list.hpp>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p{{0,3},{1,3},
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::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);
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;

example file is multiway_cut_example.cpp


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


The algorithm analysis is described in [23]