Given:

- an undirected graph G=(V,E)
- a nonnegative cost function c(u,v)
- a set of terminals S ⊆ V : {s
_{1}, s_{2}, ... s_{k}}

- a multiway cut C ⊆ E such that the removal of all edges in C from E disconnects each terminal from all the other terminals.
- cost of C: ∑
_{e∈ C}c(e) should be minimized.

The problem of finding a minimum weight multiway cut is NP-hard for any fixed k ≥ 3.

When k=2, it is the minimum s-t cut problem which can be solved in polynomial time using Maximum Flow algorithm.

- For each i = 1, 2, ..., k, compute a minimum weight isolating cut for s
_{i}, say C_{i}.

- C = C
_{1}∪ C_{2}∪ ... ∪ C_{k}- C_{j}in which C_{j}is the cut with the maximum weight.

- Output C.

- An isolating cut for s
_{i}is a set of edges whose removal disconnects s_{i}from the rest of the terminals.

Notice that C contains k-1 sets of isolating cut and the removal of C from the graph G disconnects every pair of terminals, so C is a multiway cut.

- Let A be the set of edges in the optimal solution.

- Remove all edges in A from the graph:

- create k connected components, no more, no less;

- every terminal s
_{i}is in a different connected component;

- let A
_{i}⊆ A be the isolating cut for s_{i}.

- create k connected components, no more, no less;
- Every edge appears in exactly two sets, so:

∑_{i=1}^{k}c(A_{i}) = 2c(A) = 2 • OPT

- C
_{i}is the minimum isolating cut for s_{i}, so:

c(C_{i}) ≤ c(A_{i})

- The isolating cut with the heaviest cost C
_{j}is discarded, so:

c(C_{j}) ≥ 1/k ∑ c(C_{i})

- Finally we get:

c(C) ≤ (1-1/k) ∑_{i=1}^{k}c(C_{i}) ≤ (1-1/k) ∑_{i=1}^{k}c(A_{i}) ≤ (2-2/k) OPT

**An example showing this ratio is tight:**

The blue cut is the approximation solution, c(C) = 6-3ε

The red cut is the OPT solution, c(A) = 4

This is an interesting relaxation of linear program by Gruia Calinescu, et al.

- Minimize ∑
_{(u,v)∈ E}c(u,v)d(u,v) subject to:

- d(u,v) = 1/2 ∑
_{i=1}^{k}| x_{u}^{i}- x_{v}^{i}| (u,v) ∈ E

- x
_{v}∈ Δ_{k}∀ v ∈ V

- x
_{t}= e_{t}∀ t ∈ S

- d(u,v) = 1/2 ∑

**Explainations:**

- Δ
_{k}denotes the k-1 simplex, a k-1 dimensional convex polytope in R^{k}defined by:

{x ∈ R^{k}| x ≥ 0 and ∑_{i=1}^{k}x_{i}= 1} .

- For x ∈ R
^{k}, ||x|| is its L_{1}norm, ||x|| = ∑_{i=1}^{k}||x_{i}|| .

- e
_{t}denotes the unit vector given by (e_{j})^{j}= 1, (e_{j})^{i}= 0 for all i¬= j.

- Vertices of G are mapped to the points in Δ
_{k}, terminals are mapped to simplex corners. - Every vertex v is associated with a k-dimensional vector x
_{v}, with each component between 0 and 1. For k = 7: x_{v}= (x_{v}^{1}, x_{v}^{2}, x_{v}^{3}, x_{v}^{4}, x_{v}^{5}, x_{v}^{6}, x_{v}^{7}) - An integral solution maps each vertex of G to a vertex of the simplex, respectively. Each edge (u,v) has length 0 or 1. Edges of length 1 form a multiway cut.Optimal integral solution corresponds to an optimal multiway cut.

- Terminals have forms:

x_{3}= (0,0,1,0,0,0,0); x_{7}= (0,0,0,0,0,0,1).

- Non-terminals:
- Integer solution:
- x
_{v}^{t}= 1 iff v and t in the same partition. - x
_{v}^{t}= 0 iff v and t in the different partitions. - Exactly one coordinate is 1, all others are 0.

- x
- Fractional solution:
- 0 ≤ x
_{v}^{t}≤ 1 - ∑
_{t=1}^{k}x_{v}^{t}= 1 - x
_{v}= (0, 0.2, 0, 0, 0.4, 0, 0.4)

- 0 ≤ x

- Integer solution:
- The distance between two vertices is defined as:

d(u,v)=1/2 ∑_{t=1}^{k}| x_{u}^{t}- x_{v}^{t}|

- d(u,v)=0 ⇒ u and v in the same partition;
- d(u,v)=1 ⇒ u and v in different partitions;e.g. d(s
_{1},s_{2}) = 1/2(|1-0|+|0-1|+|0-0|) = 1 in the following figure. - The fractional solution will give us 0 ≤ d(u,v) ≤ 1 , we need some technique to decide how to partition those vertices.

e.g. d(u,s_{1}) = 1/2(|0.5-1|+|0.5-0|+|0-0|) = 0.5 in the following figure.

Example of G with 3 terminals {s_{1}, s_{2}, s_{3}} and 3 non-terminals {u, v, w}:

In this example, the optimal fractional solution has cost 7.5:

- 6 edges with weight 2, 3 edges with weight 1, all edges has distance 1/2, so,

- ∑
_{(u,v)∈ E}c(u,v)d(u,v) = (2*1/2) * 6 + (1*1/2) * 3 = 7.5 .

**How to partition node u, v and w? **

1.We need normalization before present the algorithm:

- Let A be a feasible solution to the LP.
- It's possible to construct a graph G=(V,E) such that:
- The value of A is at most A with same cost.
- For all edges (u,v)∈ E the vectors x
_{u}and x_{v}differ at most 2 coordinates.

- This can be done by dividing edges with adding dummy vertex.
- The transformation requires at most k|E| subdivisions.

- x = optimal, normalized solution of LP.
- E
_{t}= {(u,v) ∈ E | x_{u}^{t}¬= x_{v}^{t}}- edges between vertices that differ in coordinate t.
- each edge (u,v) appears in two of these sets.

- W
_{t}= ∑_{e∈ Ei}c(e)d(e)- cost of all edges in E
_{t}, weighted by the distances. - each edge with d(e) > 0 is counted twice.

- cost of all edges in E
- B(t,ρ) = {v ∈ V | x
_{v}^{t}≥ ρ}, for ρ ∈ [0,1]- set of all vertices that are with small distance to terminal t.
- v is "close" to i ⇔ x
_{v}^{t}≥ ρ

- Compute the optimal, normalized fractional solution x of LP;
- Relabel the terminals so that W
_{k}is the largest among all W_{i}; - Pick random σ in two permutations: {(1,2,...,k-1,k), (k-1,k-2,...,1,k)};
- Pick random ρ∈[0,1];
- For i = 1 to k-1 do V
_{σ(i)}=B(i,ρ)-∪_{j<i}V_{σ(j)}; - V
_{k}= V - ∪_{i<k}V_{i}; - Return C = {(u,v) ∈ E | u∈ V
_{i}, v∈ V_{j}, i ¬= j} .

**Analysis of the approximation ratio: 3/2 - 1/k **

1. Intuition:

- The probability of an edge being cut = the probability of ρ falling in between the interval (x
_{u}^{i},x_{v}^{i}) = the distance of these two interval.

Every color represents a choice of ρ, only when the color line falls into interval (u,v), the edge (u,v) is cut by partition v into S1, partition u into S3.

This gives us probability d(e).

With the same ρ but different σ:

- In the left graph, set 1 is partitioned first, u and v are both picked, edge (u,v) is hidden to set 2.
- In the right graph, set 2 is partitioned first, with the same ρ, u is partitioned into set 2, v is partitioned into set 1. Edge (u,v) is made a cut.
- So σ increase the probability of an edge being cut.
- This gives us probability d(e)/2.

The summation of previous d(e) and d(e)/2 gives us the approximation ratio 3/2. And since the heaviest cut is discarded, we get 3/2-1/k.

2. Formal analysis:

(1) If e ∈ E - E_{k}, Prob[e∈ C]≤ 1.5• d(e)

- Let e = (u,v), let i and j be the coordinates in which x
_{u}and x_{v}differ. - There are two cases: the intervals [x
_{u}^{i},x_{v}^{i}] and [x_{v}^{j},x_{u}^{j}] either overlap or disjoint, but having the same length d(e):

- vertices u and v can end up in one of 3 sets, V
_{i}, V_{j}, V_{k}. (other than these 3 sets make no difference) - if ρ ∈ [0,1]-(α ∪ β) , u and v end up in the same set, ⇒ edge e will not be in the cut.
- P
_{1}= Pr[ρ ∈ (α ∪ β)] = |α| + |β|

- P
- special case:
- ρ ∈ α and σ(j) < σ(i)
- both u and v will end up in S
_{j} - P
_{2}= Pr[(ρ ∈ α) and (σ(j) < σ(i))] = |α|/2

- Pr[e ∈ C] = P
_{1}- P_{2}= |β| + |α|/2 ≤ 1.5d(e)

(2) If e ∈ E_{k}, Prob[e∈ C]≤ d(e)

- Let e=(u,v) and i and k be the coordinates in which x
_{u}and x_{v}differ.- σ(i) < σ(k) because set k is always the last set in the two permutations;
- u and v will end up in different sets if ρ falls between interval x
_{u}and x_{v}:

Pr[(u,v) ∈ C] = |x_{u}^{i}- x_{v}^{i}| = d(e)

(3) From the analysis of (1) and (2):

E[c(C)] = ∑_{e∈ E}c(e)Pr[e∈ C] = ∑_{e∈ E-Ek}c(e)Pr[e∈ C] + ∑_{e∈ Ek}c(e)Pr[e∈ C] ≤ 1.5 ∑_{e∈ E-Ek}c(e)d(e) + ∑_{e∈ Ek}c(e)d(e) = 1.5 ∑_{e∈ E}c(e)d(e) - 0.5 ∑_{e∈ Ek}c(e)d(e) ≤ (1.5-1/k) • OPT_{f}

**Discussion:**

- The approximation ratio 3/2-1/k is not tight.
- According to Gruia Calinescu, et al, the worst case integrality ratio is 16/15 when k=3.
- According to David Karger, et al, the integrality ratio 12/11 with k=3 using a different relaxation: Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut

[1] Vijay V. Vazirani

[2] E. Dahlhaus, et al.

[3] Gruia Calinescu, et al.