Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s_1, s_2,\ldots s_k$ are in $V$. The goal is to find a minimum set of edges in $E$ whose removal leaves all terminals in different components.

  1. How do we show that this problem can be solved exactly in polynomial time when $k= 2$?

  2. How do we get an approximation algorithm with ratio at most 2 for the case when $k \geq 3$?

share|improve this question

migrated from cstheory.stackexchange.com Dec 6 '12 at 7:14

This question came from our site for theoretical computer scientists and researchers in related fields.

1  
Why do you want "an approximation algorithm with ratio at most 2 for the case when k =3", and how do you know it can be solved in polynomial time for k=2 ? –  Suresh Dec 2 '12 at 23:11
    
For some hints: T. C. HU; E. DAHLHAUS, D. S. JOHNSON, C. H. PAPADIMITRIOU,E D. SEYMOUR, AND M. YANNAKAKIS –  Yixin Cao Dec 2 '12 at 23:58
1  
This sounds like an exercise problem. What have you tried? –  Raphael Dec 6 '12 at 10:18

1 Answer 1

Minimum $k$-Multiway Cut

Given a graph $G =(V,E)$ and a set of terminals $S=\{s_1, s_2, \dotsc, s_k\} \subseteq V$ find a minimum set of edges $E' \subseteq E$ whose removal separates each pair of terminals in $S$.

Case when $k=2$

For the case when $k=2$ Minimum $k$-Multiway cut is exactly the Minimum $s$-$t$ Cut problem. To see this simply let $(s_1, s_2) = (s,t)$ and compute a min $s$-$t$ cut. This can be solved in polynomial time by various Maximum-Flow algorithms.

Case when $k \geq 3$

We can design a very simple 2OPT approximation algorithm for the $k$-Multiway Cut problem. For each $s_i$, where $1 \leq i \leq k$, collapse $S \setminus \{s_i\}$ into a single node $t_i$. Compute a min $s_i$-$t_i$ cut and call it $C_i$. Repeat this for each possible $s_i$. Output $C = \bigcup_{i=1}^k C_i$.

Claim: $|C| \leq 2 \textrm{OPT}$

Let $A$ be the optimal multiway cut and let $A_i$ be a cut that separates $s_i$ from the rest of the graph. Since each edge in $A$ is adjacent to 2 components, each edge must be in two of the cuts $A_i$. Hence, $$\begin{align*}&\sum_i |A_i| = 2|A| &(*)\end{align*}.$$ Further, since $C_i$ is a minimal cut, $|C_i| \leq |A_i|$. This fact together with $(*)$ implies that our algorithm achieves a $2\mathrm{OPT}$ approximation ratio.

Claim: $\text{Proposed algorithm runs in polynomial time}$

The algorithm requires $k$ calls to a Minimum $s$-$t$ cut procedure. Since we only make a constant number of calls to a polynomial-time algorithm, our resulting algorithm is still polynomial.

You can further improve this to $(2 - \frac{2}{k})\mathrm{OPT}$ by dropping the heaviest cut. Beating that bound requires a slightly more advanced LP rounding schema.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.