Multi-Terminal Cuts - Applications and Verifying validity of an approximation algorithm

Question

First thing first - I am not a CS guy. I am EE student (Systems and Signals). So it would help if you didn't use any big words :)

The Multi-terminal cut the input is a graph G and a subset T of its vertices. The task is to remove the minimum number of edges from G such that there is no path connecting any distinct vertices of T. Dalhaus et all showed that its NP-Hard for $k\ge 3$ for arbitrary.

Question - Why is this class of problem important? Do they show up in some engineering application.

A few years ago I found a simple algorithm proposed as an approximation of the Multi-terminal cut problem for arbitrary weighted slow-coherent graphs. (Strong connected components which are weakly connected with each other). I did a performance analysis of the algorithm from a linear algebra point of view and was able show that algorithm should be work for these classes of graphs.

I would like to take the algorithm and apply it to an application area and see how it fares compared to the "standard".

Answer 1

The multi-terminal cut problem (which is also known as the multiway cut problem) has many important applications. In the more general setting, each edge $e$ has a cost $c_e \ge 0$. The goal is to remove a minimum cost set of edges such that in the resulting graph there is no path between any two vertices in $T$. Here is an application in distributed computing.

Each vertex represents an object, and an edge $e$ of cost $c_e$ between them represents the cost of communication between the objects. The objects have to be partitioned to reside on $k$ different machines, with special object $s_i$ residing on the $i^{th}$ machine. The goal is to partition the objects residing on the $k$ machines in such a way that the communication cost between the machines is minimized.