# Multiway cut – 2

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 = ${s_1, s_2, ..., s_k}$ of k vertices, find a cut of minimum size (in terms of weights of edges) that separates each $s_i$ from all other vertices in S.

Algorithm:

1. Find an isolating cut for each $s_i$. Call each such isolating cut $C_i$.

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

The above set of edges is a multiway cut.

We saw how the set of edges $C_1 \cup C_2 \cup ... \cup C_k$ 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, $C_i$ having minimum size. It then removes the edges of cut, $C_i$ from the graph, G to get a new graph G’. The vertex $s_i$ 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 $G_1 = G.$ and $S_1 = S.$

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 $S_i$) – $C_i$ for each vertex in $S_i.$

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

4. Remove the edges of $C_j$ from $G_i$ to get a new graph, $G_{i+1}$.

5. Add the edges of $C_j$ to C. i.e. $C = C \cup C_j.$

6. Remove vertex, $s_j$ from $S_i$ to get a new set, $S_{i+1}.$

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:

Example for multiway cut: the edge weights are indicated alongside the edges.

In the above example:

The minimum isolating cut for $s_3$ has value = 20. (One such candidate for $C_3$ is the set of edges { {s2,s3), {s3,C}}.
The minimum isolating cut for $s_1$ 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 $s_2$ 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 $C_1$ or $C_2$ since both have equal minimum value. Suppose, we add $C_1$ to C. Now, C = {{A,B}, {A,C}}.
Remove edges of $C_1$ from G, and recompute minimum isolating cuts for $s_2$ and $s_3$ on the new set, S = {s2, s3}.
We get a minimum isolating cut of value = 10 for both $s_2$ and $s_3$. 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):

Example for multiway cut

Note: In the above diagram, the letter e has been used to denote $\epsilon > 0$.

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

Performance of first algorithm on above instance:
Value of $C_1 = 2 - 2 \epsilon$.
For all other vertices in S, value of $C_i = 2 - \epsilon.$

Therefore, the value of cut produced by algorithm = $(k-2) \times (2-\epsilon) + (2 - 2 \epsilon).$

Performance of second algorithm on above instance:
Value of minimum $C_i$ is $2- 2 \epsilon$ given by $C_1$. On removing $C_1$ from G and $s_1$ 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 = $(k-2) \times 1 + (2 - 2 \epsilon)$.

Verify that for large values of k, as $\epsilon$ —> 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:

A tight example for both algorithms.

(Note: The letter, e has been used in the diagram to represent, $\epsilon >0$.

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 = $(k-1) \times (2 - \epsilon)$.

3. The second algorithm produces a cut of value = $(k-1) \times (2 - \epsilon).$

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

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