# Multiway Cut

A cut, C in a graph, G= (V, E) is a set of edges, whose removal from G disconnects G. i.e. G’ = (V, E – C) is disconnected. (A graph is said to be connected if there exists a path between any two vertices in the graph. Hence, a graph is said to be disconnected if there exist two vertices in the graph, say u and v, such that there exists no path between u and v in the graph.)

An s-t cut, C is a set of edges whose removal from the graph, disconnects s and t.

(Note: Throughout this discussion, we shall talk only about undirected, edge-weighted, connected graphs. Also, all edge weights are integers.)

Size of a cut: This means the total weight of all edges forming the cut.

We want to disconnect the graph; but we want to do so by removing as few (in terms of weight) edges as possible. That, we wish to find a cut of minimum size. Such a cut is called a min – cut.

Example for min – cut:

Min Cut example: All edges in the graph have weight = 20, other than the 3 highlighted edges. Those 3 edges form the min cut.

An s-t min cut, as is clear from the name, is a cut of minimum size that separates vertex s from vertex t.

Example for s- t min cut:

Example for s-t min cut

(The highlighted edges form an s-t min cut of value = 40. Note that the min cut value for this graph is 5 (obtained by removing edge {a,b}.)

=========

A multiway cut is a generalization of an s-t cut.

Here, instead of two vertices, s and t, we have to separate a set of k vertices, ${s_1, s_2, ..., s_k}$ from each other.

In other words, find a set of edges, say C, such that on removing C from the graph, there exists no path between $s_i$ and $s_j$ for any $i, j \in {1,2, ..., k}$.

Our task is to find a multiway cut of minimum size.

Example of multiway cut:

By removing all edges shown in the figure, we can separate vertices, s1, s2, .., sk, from one another. (Note that within each ellipse around each si, there may be a number of vertices and edges between those vertices. They have not been shown for sake of clarity.)

(The above example shows a multiway cut.)

========

Question: How do you find a multiway cut of minimum size?

It turns out that it is hard to find such a cut in polynomial time. But that’s not the end of the story. What we can do efficiently (in general, an algorithm is efficient if it runs in polynomial time) is to find a multiway cut that is within a factor of 2 from the optimal. In other words, if the value of the optimal multiway cut of a graph, G is $OPT (G)$, our algorithm will produce a cut of value $\leq 2 \times OPT (G)$ for every graph, G.

(So, even though we don’t find an optimal cut, we find one that is guaranteed to be “close” to optimal.)

========

Even though, we do not know of any efficient algorithm, for solving a multiway cut problem exactly for arbitrary values of k, we do know how to solve it efficiently for k = 2. (Note that for k = 2, the multiway cut problem is just the s-t cut problem. An optimal s-t cut can be found efficiently. [It is actually quite simple to do it; but that is not our concern here.] )

We will use this efficient s-t min cut algorithm to find our approximate multiway cut.

————–

Let us review once again what we want. Let us denote by S the set of k vertices, ${s_1, s_2, ..., s_k}$.

We want to remove a set of edges, such that on their removal:
– there exists no path from $s_1$ to $s_2$, $s_1$ to $s_3$, and so on till $s_1$ to $s_k$.
– there exists no path from $s_2$ to $s_1$, $s_2$ to $s_3$, and so on till $s_2$ to $s_k$.
– there exists no path from $s_3$ to any of the other vertices in S.
– and so on, for each vertex in the set, S.

The above explanation of the problem actually provides us with a straightforward algorithm for the same.

Take vertex, $s_1$. Find a set of edges, removing which would disconnect $s_1$ from every other vertex in S.
Let $C_1$ be such a set of minimum size (i.e. minimum total weight).

How do we find C_1? Simple; we want a min cut that separates $s_1$ from all other vertices of S. What we’ll do is merge all these other vertices of S into one single vertex, call it t. Find an s-t min cut with $s_1$ as the vertex, s, and the merged vertex as t.

(Merging: When we merge any two or more vertices, the edges between these merged vertices disappear. The other edges that were incident upon these vertices, remain as such, and are now incident upon the new merged vertex.

Example for merging vertices:

The graph on the right is obtained by merging vertices, C, D, E and F into one "super-vertex" denoted by {C,D,E,F}. Note that there are multiple edges between the "super-vertex" and some other vertices of the graph.

(Each of the edges {F,G} and {E,G} translates into an edge between the super-vertex and G. Hence, there are 2 edges between {C,D,E,F} and G.)

Therefore, using the efficient algorithm for finding an s-t min cut, we can compute $C_1$. On removing the edges of $C_1$, vertex $s_1$ will be disconnected from all other vertices in S.

So, the first part of our job is done (disconnecting $s_1$ from all others in S.)

(Note: We call $C_1$ as an “isolating cut” for vertex, $s_1$.)

Similarly, find isolating cut $C_2$ corresponding to vertex $s_2$. On removing the edges of $C_2$, $s_2$ is disconnected from every other vertex of S.

Therefore, by removing the union of $C_1$ and $C_2$, we can disconnect $s_1$ and $s_2$ from every other vertex in S (and obviously, from each other also).

Now, you get an idea of how to proceed, right?

Find an isolating cut $C_i$ corresponding to each vertex, $s_i$ in the set, S.

The union of all these isolating cuts, i.e. $C_1 \cup C_2 \cup ... \cup C_k$ is a multiway cut separating $s_1, s_2, ..., s_k$ from one another.

=========

Question: We had claimed that the cut produced by the algorithm is always within a multiplicative factor of 2 within the optimal. How do we prove this?

Let us call the cut produced by the above algorithm as C. i.e. $C = C_1 \cup C_2 \cup ... \cup C_k$.

Let us call the optimal cut as A.

Now, on removing the edges of A from G, we would get k (disjoint) connected components in the graph, one connected component for each vertex, $s_i$.

Let $A_1$ be the subset of edges from A, that is incident upon the connected component of $s_1$.

Graph showing A1. (A1 is the set of dashed edges.) (Note that vertices and edges within the connected components of vertices other than s1 have not been shown. Also, the edges between the various connected components other than the one containing s1 have not been shown, for sake of clarity.)

As is quite obvious, $A = A_1 \cup A_2 \cup ... \cup A_k$.

It is also clear that each edge of A appears in exactly two $A_i 's$. (If an edge of A is between the connected component of vertex $s_i$ and $s_j$, then it appears in the sets $A_i$ and $A_j$. )

From this, we have that:

$\sum_{i=1}^{k} w(A_i) = 2 \times w(A)$.  —————————Eqn. (1)

Here, w(X) denotes the total weight of edges in set, X.

Now, we know that $C_1$ is an isolating cut of minimum size for $s_1$.

Therefore, $w(C_1) \leq w(A_1)$.

Similarly, $w(C_i) \leq w(A_i)$ for all $i \in {1, 2, ..., k}$.

Therefore, $\sum_{i=1}^{k} C_i \leq \sum_{i=1}^{k} A_i$.

Combining the above equation with Eqn. (1), we get that:-

$\sum_{i=1}^{k} C_i \leq 2 \times w(A)$.

i.e. the cut produced by our algorithm is always within a factor of 2 of the optimal multiway cut.

In other words, we are done. 🙂

Points to ponder:

1. Do we necessarily need to take the union of all k sets $C_1$ till $C_k$ to obtain a multiway cut? What if we take the union of only k-1 of these sets? Will that union be a valid multiway cut?

2. As an extension of the above point: which k-1 sets should we choose in order to minimize the size of the cut produced? (Hint: you can discard the heaviest among the $C_i 's$ and output the union of the rest.) We know that outputting the union of all k sets results in a factor-2 approximation algorithm. What is the approximation factor for this improved algorithm? (Hint: Prove that the approximation factor is (2 – 2/k). )

(The topic of multiway cut is dealt in Chap. 4 of “Approximation Algorithms” by Vijay Vazirani.)