<p>The multi-terminal cut problem (which is also known as the <em>multiway cut</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-12-19T10:20:35.377Z
2013-12-19T10:20:35.377Z
Arindam Pal
<p>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 :)</p>

<p>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.</p>

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

<p>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.</p>

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

<graph-algorithms><approximation-algorithms>
Multi-Terminal Cuts - Applications and Verifying validity of an approximation algorithm
RahulD
# Multi-Terminal Cuts - Applications and Verifying validity of an approximation algorithm

(Asked by: username_0 on 2013-12-16)

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

**Tags:** graph-algorithms, approximation-algorithms


---

## 1 answers

### Answer by username_1 on 2013-12-19. Score: 2 | Accepted answer

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.


---

