[SOLVED] CS database algorithm Lecture 8 (Adv): Kargers algorithms

Lecture 8 (Adv): Kargers algorithms
The University of Sydney Page 1

Randomization
Algorithmicdesignpatterns. Greed.
Divide-and-conquer.
Dynamicprogramming. Networkflow.
Randomization.
Randomization: Allow fair coin flip in unit time.
Why randomize? Can lead to simplest, fastest, or only known
algorithm for a particular problem.
Examples: Symmetry breaking protocols, graph algorithms, quicksort, hashing, load balancing, Monte Carlo integration, cryptography.
in practice, access to a pseudo-random number generator
The University of Sydney
Page 2

13.2 Global Minimum Cut
Input: A connected, undirected graph G = (V, E). For a set SIV let d(S) = {(u,v)IE : uIS, vIVS}.
S=VS
S
S
v2 v3
v6v5 v4 v7 v1
Aim: Find a cut (S, S) of minimum cardinality.
|d(S)| = 4
The University of Sydney
Page 3

13.2 Global Minimum Cut
Input: A connected, undirected graph G = (V, E). For a set SIV let d(S) = {(u,v)IE : uIS, vIVS}.
v2 v3
S
S
|d(S)| = 2
v6v5 v4 v7 v1
Aim: Find a cut (S, S) of minimum cardinality.
The University of Sydney
Page 4

13.2 Global Minimum Cut
Applications: Partitioning items in a database, identify clusters of related documents, network reliability, network design, circuit design, TSP solvers.
Network flow solution.
Replace every edge (u, v) with two directed edges (u, v) and (v, u).
Pick some vertex s and compute min s-v cut separating s from each other
vertex v I V.
Running time: O((n-1)MaxFlows)
The University of Sydney Page 5

Kargers Contraction Algorithm
Definition: A multigraph is a graph that allows multiple edges
between a pair of vertices.
3
The University of Sydney
Page 6

Kargers Contraction Algorithm
Definition: A multigraph is a graph that allows multiple edges
between a pair of vertices.
Algorithm:
3
1. 2.
3.
Start with the input graph G=(V,E). While |V|>2 do
Contract an arbitrary edge (u,v) in G. Return the cut (only one possible cut).
The University of Sydney
Page 7

Kargers Contraction Algorithm
Let G=(V,E) be a multigraph (without self-loops). Contract an edge e=(u,v)IE Ge
Replace u and v by single new super-node w
Replace all edges (u,x) or (v,x) with an edge (w,x) Remove self-loops to w.
abc
abc
udv w f e contract u-v f
The University of Sydney
Page 8

Kargers Contraction Algorithm
Definition: A multigraph is a graph that allows multiple edges between a pair of vertices.
Algorithm:
1. 2.
3.
Start with the input graph G=(V,E). While |V|>2 do
Contract an arbitrary edge (u,v) in G. Return the cut (only one possible cut).
|d(S)|
The University of Sydney
Page 9

The University of Sydney
Kargers contraction algorithm
Page 10

The University of Sydney Page 11

Kargers Contraction Algorithm
Observation: An edge (u,v) contraction preserves those cuts where u and v are both in S or in S.
ux

x
v
y
w
y
The University of Sydney
Page 12

Kargers Contraction Algorithm
Observation: An edge (u,v) contraction preserves those cuts where u and v are both in S or in S.
ux
S S
y
x
S
w
y
S
v
The University of Sydney
Page 13

Kargers Contraction Algorithm
Observation: An edge (u,v) contraction preserves those cuts where u and v are both in S or in S.
S ux

S x
y
w
y
S
v
S
The University of Sydney
Page 14
If u,vIS then dG(S) = dGe(S). (with u and v replaced with w)

Algorithm: General idea
Contract n-2 edges two vertices remain in G
The University of Sydney Page 15

Algorithm: General idea
Contract n-2 edges two vertices remain in G
The two vertices in G correspond to a partition (S,S) in G.
The University of Sydney Page 16

Algorithm: General idea
Contract n-2 edges two vertices remain in G
The two vertices in G correspond to a partition (S,S) in G. The edges remaining in G corresponds to dG(S).
Output dG(S).
If we never contract edges from a minimal cut d(S*) then the algorithm will report d(S*).
How do we select the edges?
The University of Sydney
Page 17

Kargers Contraction Algorithm
Algorithm:
1. 2.
Start with the input graph G=(V,E). While |V|>2 do
Contract an arbitrary edge (u,v) in G. Return the cut S (only one possible cut).
3.
Algorithm: Since S* is a minimum cut it has few edges!
Claim: This algorithm has a reasonable chance of finding a minimal cut.
The University of Sydney
Page 18

Prove the claim
Claim: The algorithm returns a minimal cut with probability 3 2/n2.
Proof:
Consider a global min cut (S,S) of G. Let d be edges with one endpoint in S and the other in S.
Let k = |d| = size of the min cut.
S
d
S
The University of Sydney
Page 19

Prove the claim
Claim: The algorithm returns a minimal cut with probability 3 2/n2.
Proof:
Consider a global min cut (S,S) of G. Let d be edges with one endpoint in S and the other in S.
Let k = |d| = size of the min cut.
S
d
S
Step 1: contract an edge in d with probability k/|E|. Size of E?
The University of Sydney
Page 20

Prove the claim
Claim: The algorithm returns a minimal cut with probability 3 2/n2.
Proof:
Consider a global min cut (S,S) of G. Let d be edges with one endpoint in S and the other in S.
Let k = |d| = size of the min cut.
S
d
S
Step 1: contract an edge in d with probability k/|E|.
Every node has degree 3 k otherwise (S,S) would not be min-cut. |E|312kn.
The University of Sydney
Page 21

Prove the claim
Claim: The algorithm returns a minimal cut with probability 3 2/n2.
Proof:
Consider a global min cut (S,S) of G. Let d be edges with one endpoint in S and the other in S.
Let k = |d| = size of the min cut.
S
d
S
Step 1: contract an edge in d with probability k/|E|. with probability 2/n.
The University of Sydney
Page 22

Prove the claim
Claim: The algorithm returns a minimal cut with probability 3 2/n2.
Proof:
Consider a global min cut (S,S) of G. Let d be edges with one endpoint in S and the other in S.
Let k = |d| = size of the min cut.
Step 1: contract an edge in d with probability 2/n.
Observation:
S
d
S
The minimum degree in any (intermediate) multigraph is at least k. (Otherwise there would be a smaller cut)
Specifically this means that if an intermediate multigraph has n vertices, it will have at least nk/2 edges.
The University of Sydney
Page 23

Prove the claim
Claim: The algorithm returns a minimal cut with probability 3 2/n2.
Proof:
Consider a global min cut (S,S) of G. Let d be edges with one endpoint in S and the other in S.
Let k = |d| = size of the min cut.
Step 1: contract an edge in d with probability 2/n.
After step i: The multigraph Gi has n-i vertices and at least (n-i)k/2 edges.
S
d
S
The University of Sydney
Page 24

Prove the claim
Claim: The algorithm returns a minimal cut with probability 3 2/n2.
Proof: Consider a global min cut (S,S) of G. Let d be edges with one endpoint in S and the other in S.
Let k = |d| = size of the min cut.
d
S
Step 1: contract an edge in d with probability 2/n. After step i: The multigraph Gi has n-i vertices
and at least (n-i)k/2 edges.
Let ei = random edge in Gi that was contracted
S
Probability that the algorithm finds minimum cut?
Pr[edges in the final graph is d] = Pr[e1, e2, , en-2 I d]
The University of Sydney
Page 25

Proof
Theorem: Pr[e1, e2, , en-2 I d] > 2/n2 Proof:
Pr[e1, e2, , en-2 I d] =
= Pr[e1I d] P Pr[ei+1I d : e1, , ei I d]
3 (1- 2 )(1- 2 )(1- 2 ) (1- 2 ) n n-1 n-2 3
= n-2n-3n-4n-5 21
=
n
2 n(n-1)
n-1 n-2 n-3
4 3
The University of Sydney
Page 26

Proof
Theorem: Pr[e1, e2, , en-2 I d] > 2/n2 Proof:
Pr[e1, e2, , en-2 I d] =
= Pr[e1I d] P Pr[ei+1I d : e1, , ei I d]
3 (1- 2 )(1- 2 )(1- 2 ) (1- 2 ) n n-1 n-2 3
= n-2n-3n-4n-5 21
n n-1 n-2 n-3
4 3
=2= n(n-1)
1 n 2
The University of Sydney
Page 27

Amplification
To amplify the probability of success, run the contraction algorithm many times.
Claim: If we repeat the contraction algorithm r 2n times with independent random choices, the probability that all runs fail is at
most
(1- 1n )r 2n (1/e)r 2
The University of Sydney
Page 28
(1- 1x )x 1/e

Amplification
To amplify the probability of success, run the contraction algorithm many times.
Claim: If we repeat the contraction algorithm r 2n times with independent random choices, the probability that all runs fail is at
most
(1- 1n )r 2n (1/e)r 2
constant
Set r = (c ln n) then probability of failure is: e-c ln n = n-c and probability of success is: 1-1/nc
The University of Sydney
Page 29

Kargers Contraction Algorithm
Algorithm:
1. 2.
3.
Start with the input graph G=(V,E). While |V|>2 do
Contract an arbitrary edge (u,v) Return the cut S (only one possible cut).
Running time?
The University of Sydney
Page 30

Kargers Contraction Algorithm
Algorithm:
1. 2.
3.
Start with the input graph G=(V,E). While |V|>2 do
Contract an arbitrary edge (u,v) Return the cut S (only one possible cut).
Running time: n-2 iterations.
each iteration requires O(n) time
O(n2)
The algorithm is iterated O(n2 log n) timestotal running time O(n4 log n).
The University of Sydney
Page 31

Improved algorithm
Improvement. [Karger-Stein 1996] O(n2 log3n).
Early iterations are less risky than later ones: probability of
contracting an edge in min cut hits 50% when n/2 nodes remain.
Run contraction algorithm until n/2 nodes remain.
Run contraction algorithm twice on resulting graph, and return best of two cuts.
Running time?
The University of Sydney Page 32

Improved algorithm
Improvement. [Karger-Stein 1996] O(n2 log3n).
Early iterations are less risky than later ones: probability of
contracting an edge in min cut hits 50% when n/2 nodes remain .
Run contraction algorithm until n/2 nodes remain.
Run contraction algorithm twice on resulting graph, and return best of two cuts.
Running time: T(n) = 2(n2+T(n/O2 ))
= O(n2 log n) [Master Thm]
The University of Sydney
Page 33

Improved algorithm
Improvement. [Karger-Stein 1996] O(n2 log3n).
Early iterations are less risky than later ones: probability of
contracting an edge in min cut hits 50% when n/2 nodes remain .
Run contraction algorithm until n/2 nodes remain.
Run contraction algorithm twice on resulting graph, and return best of two cuts.
Running time: T(n) = 2(n2+T(n/O2 ))
= O(n2 log n) [Master Thm]
Probability of success?
The University of Sydney
Page 34

Improved algorithm
Improvement. [Karger-Stein 1996] O(n2 log3n).
Early iterations are less risky than later ones: probability of
contracting an edge in min cut hits 50% when n/2 nodes remain .
Run contraction algorithm until n/2 nodes remain.
Run contraction algorithm twice on resulting graph, and return best of two cuts.
Running time: T(n) = 2(n2+T(n/O2 ))
= O(n2 log n) [Master Thm]
Probability of failure: Pr[n] (1-12Pr[n/O2 ])2 = O(1/log n)
The University of Sydney
Page 35

Improved algorithm
Improvement. [Karger-Stein 1996] O(n2 log3n).
Early iterations are less risky than later ones: probability of contracting an edge in min cut hits 50% when n/2 nodes remain .
Run contraction algorithm until n/2 nodes remain.
Run contraction algorithm twice on resulting graph, and return best of two cuts.
Running time: T(n) = 2(n2+T(n/O2 )) = O(n2 log n)
Probability of failure: Pr[n] (1-12Pr[n/O2 ])2 = O(1/log n)
The University of Sydney
Page 36
Run the algorithm c log2 n times

Improved algorithm
Improvement. [Karger-Stein 1996] O(n2 log3n).
Early iterations are less risky than later ones: probability of
contracting an edge in min cut hits 50% when n/2 nodes remain.
Run contraction algorithm until n/2 nodes remain.
Run contraction algorithm twice on resulting graph, and return best of two cuts.
Best known. [Karger 2000] O(m log3n).
faster than best known max flow algorithm or deterministic global min cut algorithm
The University of Sydney
Page 37

Reading material
Eric Vigodas lecture notes
http://www.cc.gatech.edu/~vigoda/7530-Spring10/Kargers- MinCut.pdf
The University of Sydney Page 38