# Multiway Cut

October 17, 2009 1 Comment

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

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

(*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, 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 and for any .

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

**Example of multiway cut: **

*(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 , our algorithm will produce a cut of value 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, .

We want to remove a set of edges, such that on their removal:

– there exists no path from to , to , and so on till to .

– there exists no path from to , to , and so on till to .

– there exists no path from 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, . Find a set of edges, removing which would disconnect from every other vertex in S.

Let 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 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 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:*

*(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 . On removing the edges of , vertex will be disconnected from all other vertices in S.

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

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

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

Therefore, by removing the union of and , we can disconnect and 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 corresponding to each vertex, in the set, S.

The union of all these isolating cuts, i.e. is a multiway cut separating 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. .

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

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

As is quite obvious, .

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

From this, we have that:

. —————————Eqn. (1)

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

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

Therefore, .

Similarly, for all .

Therefore, .

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

.

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 till 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 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.)

Pingback: Multiway cut – 2 « Wondrous Assortment