multy way cut and k-cut approximation

Multi way cut and k-cut :

Multi way cut and k-cut Saeed Akhoondian Amiri , under supervisor of Dr.Moazzami

Multi way cut:

Multi way cut Given a set of terminals , a multiway cut is a set of edges whose removal disconnects the terminals from each other. multiwaycut asks for the minimum weight such set.

Slide 3:

S 1 S 2 S 3 S 4

Isolating cut:

Isolating cut Define an isolating cut for S i to be a sets of edges whose removal disconnects s i from the rest of terminals.

Algorithm 4.3 (Multiway cut):

Algorithm 4.3 ( Multiway cut) For each i =1,…,k, compute a minimum weight isolating cut for S i , say C i . Discard the heaviest of these cuts, and output the union of rest, say C.

approximation factor:

approximation factor Let A , be an optimal cut in G , Let A i be a cut separating s i from the rest of graph. Then we have . Each edges of A is incident at two of these components, Hence:

approximation factor:

approximation factor Clearly A i is isolating cut for s i , since C i is a minimum weight isolating cut for s i , w( C i )≤w(A i ) . Now if skip C k ( because there is no need to this cut) we have:

Tight example for 2-2/k factor:

Tight example for 2-2/k factor A graph on a 2k vertices consisting of k-cycle and a distinct terminal attached to each vertex of the cycle. Each in edge in cycle have weight 1 and each edges connects terminal to cycle have weight . The cost by this algorithm is but the Optimal Multiway cut is given by removing K edges in cycle cost is K .

Optimal Multiway cut:

Optimal Multiway cut 1 b c g f a e d h 1 1 1

Multiway cut:

Multiway cut 1 b c g f a e d h 1 1 1

The minimum k-cut problem:

The minimum k-cut problem Problem 4.2: A set of edges whose removal leaves k connected components is called k-cut , k-cut problem asks for minimum weight k-cut .

Slide 12:

Sample 3-cut 4 4 3 3 2 2 2 10 8 5 7 b c d f a e

Simple Algorithm:

Simple Algorithm First obvious algorithm is starting G, compute a minimum cut in each connected component and remove a lightest one. This algorithm does achieve a guarantee of 2-2/k factor, but proof is hard. We will produce another algorithm with Homory-gu tree, let see what is Homory-Gu tree.

Gommory-Hu tree:

Gommory-Hu tree We have G=(V,E), Let T be a tree on vertext set V, the edges of T need not be in E. Let e be an edge in T, it’s removal from T creates two connected components. Let S and S’ be a vertex sets of this components, The cut defined buy the partition (S,S’) is the cut associated with e in G. define a weight function w’ on T:

Gommory-Hu tree:

Gommory-Hu tree Tree T, will be said Homory-Gu tree for G if: For each pair of vertices , the weight of a minimum u-v cut in G is the same as that in T. For each edge , w’(e) is the a weight of cut associated with e in G.

Homory-Gu tree construction:

Homory-Gu tree construction Bellow construction of homory-gu tree provided by animations:

Slide 17:

Initial Partition: a,b,c,d,e,f

Slide 18:

Initial Partition: a,b,c,d,e,f Select b and f a,b c,d,e,f

Slide 19:

Select b and f a,b c,d,e,f 17 4 4 3 3 2 2 2 10 8 5 7 b c d f a e

Slide 20:

Initial Partition: a,b,c,d,e,f Select b and f a,b c,d,e,f 17 c,d,e,f 17 b a Select a and b

Slide 21:

c,d,e,f 17 b a Select a and b 4 4 3 3 2 2 2 10 8 5 7 b c d f a e 18

Slide 22:

Initial Partition: a,b,c,d,e,f Select b and f a,b c,d,e,f 17 c,d,e,f 17 b a Select a and b 18 Select c and f a 18 b c,d,e 17 f

Slide 23:

Select c and f a 18 b c,d,e 17 f 4 4 3 3 2 2 2 10 8 5 7 b c d f a e 1 3

Slide 24:

Initial Partition: a,b,c,d,e,f Select b and f a,b c,d,e,f 17 c,d,e,f 17 b a Select a and b 18 Select c and f a 18 b c,d,e 17 f 13 Select d and e a 18 b c,e 17 f 13 d

Slide 25:

Select d and e a 18 b c,e 17 f 13 d 4 4 3 3 2 2 2 10 8 5 7 b c d f a e 14

Slide 26:

Initial Partition: a,b,c,d,e,f Select b and f a,b c,d,e,f 17 c,d,e,f 17 b a Select a and b 18 Select c and f a 18 b c,d,e 17 f 13 Select d and e a 18 b c,e 17 f 13 d Select d and e a 18 b 17 f 13 d 14 14 c e

Slide 27:

Select d and e a 18 b 17 f 13 d 14 c e 4 4 3 3 2 2 2 10 8 5 7 b c d f a e 15

Algorithm 4.7 mimimum k-cut:

Algorithm 4.7 mimimum k-cut Compute a Homory-Gu tree T for G. Output the union of the ligthest k-1 cuts of the n-1 cuts associated with edges of T in G; let see be this union.

Slide 29:

a 18 b 17 f 13 d 14 c e 15

Slide 30:

4 4 3 3 2 2 2 10 8 5 7 b c d f a e

Algorithm 4.7 achieve an approximation factor of 2-2/k:

Algorithm 4.7 achieve an approximation factor of 2-2/k Let A be an optimal k -cut in G , Let V 1 ,V 2 , …, V k be the k components formed by removing A from G , and let A i denote the cut separating V i from rest of graph, then:

Algorithm 4.7 achieve an approximation factor of 2-2/k:

Algorithm 4.7 achieve an approximation factor of 2-2/k Without loss of generality assume A k is the heaviest cut, the proof idea is showing that there are k-1 cuts defined by the edges of T whose weights are dominated by the weights of the cuts of A 1 ,A 2 ,…A k-1 .

Algorithm 4.7 achieve an approximation factor of 2-2/k:

Algorithm 4.7 achieve an approximation factor of 2-2/k Let B be the sets of edges of T that connects across two sets of V 1 ,V 2 , …, V k . Consider a graph on vertex set V and edges set B, and shrink each of vertex set V i to a single vertex. Throw edges away until tree remains, and Let to be the left over edges, |B’| = k-1.

Slide 34:

V k V i u v Algorithm 4.7 achieve an approximation factor of 2-2/k

Algorithm 4.7 achieve an approximation factor of 2-2/k:

Algorithm 4.7 achieve an approximation factor of 2-2/k Suppose edges corresponds to set V i in this manner. The weight of minimum u-v cut in G, is w’( u,v ), since A i is a u-v cut in G, w(A i )≥w’( u,v ). Since:

Tight example:

Tight example 1 b c g f a e d h 1 1 1

Slide 37:

2 b c g f a e d h 2 2

Tight example for 2-2/k factor:

Tight example for 2-2/k factor A graph on a 2k vertices consisting of k-cycle and a distinct terminal attached to each vertex of the cycle. Each in edge in cycle have weight 1 and each edges connects terminal to cycle have weight . The cost by this algorithm is but removing K edges in cycle cost is K .