# Multiway cut – 2

October 19, 2009 Leave a comment

In the previous post on this topic, we saw an algorithm with an approximation guarantee of 2 for the multiway cut problem. Some guidelines were also given on developing a factor (2-2/k) approximation algorithm based on the ideas of the original algorithm.

Let us briefly review that.

**Problem: Given a set, S = of k vertices, find a cut of minimum size (in terms of weights of edges) that separates each from all other vertices in S.**

**Algorithm:**

*1. Find an isolating cut for each . Call each such isolating cut .*

*2. Output the union of the k-1 lightest isolating cuts. (i.e. exclude the heaviest of the and output the union of the rest.)*

*The above set of edges is a multiway cut.*

We saw how the set of edges formed a 2 – factor approximation to the optimal cut. Using this fact, convince yourself that the above algorithm outputs a (2-2/k) factor approximation of the optimum.

**Another multiway cut algorithm:**

We now present a mulitway cut algorithm that performs no worse than the above (2-2/k) factor algorithm, and indeed performs better than the above in examples which we will see.

The algorithm inherits the idea of finding an isolating cut for each vertex in the set, S. Then, it performs a greedy choice, and picks the isolating cut, having minimum size. It then removes the edges of cut, from the graph, G to get a new graph G’. The vertex is removed from the set, S. The same procedure is repeated on this new graph. (i.e. the isolating cuts are again computed for each of the k-1 vertices left in S, and the minimum cut is selected for removal from the graph.)

Once the above procedure is repeated k-1 times, we get the required multiway cut, which has an approximation guarantee of (2-2/k), and which additionally performs better than the above (2-2/k) factor algorithm in specific test cases.

*The algorithm is repeated below step-wise.*

*1. Let and *

*Initially, i = 1. The required multiway cut, C is initially the Null Set.*

*Repeat the following (Steps 2-7) k-1 times.*

*2. Compute isolating cuts (wrt vertices in ) – for each vertex in *

*3. Let be the minimum of the cuts computed in the previous step.*

*4. Remove the edges of from to get a new graph, .*

*5. Add the edges of to C. i.e. *

*6. Remove vertex, from to get a new set, *

*7. Increment i by one.*

*End of algorithm.*

*The set, C is the required multiway cut.*

—–

**Things to think about:**

1. Convince yourself that k-1 iterations are sufficient to generate a multiway cut. (i.e. after k-1 iterations, each of the vertices in set, S is disconnected from all other vertices in S.)

2. Can you see why this algorithm will generate a cut that is no worse than the cut produced by the earlier (2-2/k) factor algorithm.

At each step , we remove a particular vertex from the set, S, and recompute the values of the isolating cuts for the remaining vertices, based on this new S. Can you see why this could lead to a better isolating cut for a particular vertex in S than was possible under the earlier algorithm.

Let us consider an example:

In the above example:

The minimum isolating cut for has value = 20. (One such candidate for is the set of edges { {s2,s3), {s3,C}}.

The minimum isolating cut for has value = 15. There can be more than one such cut with value = 15. Let the choose this one: {{A,B}, {A,C}}.

Similarly, value of minimum isolating cut for is 15; and one such cut is given by: {{s2,B}, {s2,s3}}.

Now, how would the first algorithm proceed?

The union of the 2 lightest isolating cuts is outputted. Hence, the multiway cut produced by the algorithm is: {{A,B}, {A,C}, {s2,B}, {s2,s3}}. The value of this cut is 30.

How does the 2nd algorithm perform in this example?

Take a minimum value cut from the set of isolating cuts and add it to C. We can add either or since both have equal minimum value. Suppose, we add to C. Now, C = {{A,B}, {A,C}}.

Remove edges of from G, and recompute minimum isolating cuts for and on the new set, S = {s2, s3}.

We get a minimum isolating cut of value = 10 for both and . This is given by the edge {s2,s3}.

Add this edge to C, and we are done.

Therefore, C = {{A,B}, {A,C}, {s2,s3}}.

Value of this multiway cut = 25.

Hence, we can see how the 2nd algorithm performs better than the first in this example.

On a separate note, **convince yourself that the second algorithm will perform no worse than the first on any input graph.**

———

Another example (here the second performs asymptotically twice as better as the first):

Note: In the above diagram, the letter e has been used to denote .

The set, S consists of k vertices, through as shown. (The diagram is for k=5)

*Performance of first algorithm on above instance:*

Value of .

For all other vertices in S, value of

Therefore, the value of cut produced by algorithm =

*Performance of second algorithm on above instance:*

Value of minimum is given by . On removing from G and from S, we find that the values of all other isolating cuts become equal to one. (See the diagram.) We proceed through the algorithm as specified to get cut, C.

Value of cut, C thus produced = .

Verify that for large values of k, as —> 0, the ratio of values of the two cuts approaches 2.

*Hence, the second algorithm performs twice as better asymptotically in this case.*

3. Consider this example:

(Note: The letter, e has been used in the diagram to represent, .

*Verify for yourself the following: *

*1. The optimal multiway cut for the above instance is of value = k. (Consider removing all edges of the cycle.) *

*2. The first algorithm produces a cut of value = . *

*3. The second algorithm produces a cut of value = *

*4. Asymptotically, both algorithms achieve an approximation factor of (2-2/k). *

*(I’m sorry for any errors in this post.)
*