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:

multiway_alg2

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

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.

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

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: