This is a Multy way cut and k-cut approximation for vazirani book.

Comments

Posting comment...

Premium member

Presentation Transcript

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 .

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.