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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.