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

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