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.

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

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.

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.

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

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

One Response to Multiway Cut

  1. Pingback: Multiway cut – 2 « Wondrous Assortment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: