Understanding Randomized Algorithms and Their Applications

CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 32: Randomized algorithms

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance.

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance. Computers cannot produce true randomness, but can give pseudo-randomness that is good enough for most applications.

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance. Computers cannot produce true randomness, but can give pseudo-randomness that is good enough for most applications. in C++, rand() % 100 will give you a random integer r (uniformly) between 0 and 99.

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance. Computers cannot produce true randomness, but can give pseudo-randomness that is good enough for most applications. in C++, rand() % 100 will give you a random integer r (uniformly) between 0 and 99. Simple Example I: In a list of 60,000 people in which half are males and half are females, find (any) person who is a female.

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance. Computers cannot produce true randomness, but can give pseudo-randomness that is good enough for most applications. in C++, rand() % 100 will give you a random integer r (uniformly) between 0 and 99. Simple Example I: In a list of 60,000 people in which half are males and half are females, find (any) person who is a female. Algorithm. 1. loop 10 times: 1.1 randomly pick a person in the list; 1.2 If this is a female, stop; 2. report(fail) randomly pick a person in the list is implemented as: 1.1.1 r = (rand() % 60,000) + 1; 1.1.2 pick the r-th person in the list;

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance. Computers cannot produce true randomness, but can give pseudo-randomness that is good enough for most applications. in C++, rand() % 100 will give you a random integer r (uniformly) between 0 and 99. Simple Example I: In a list of 60,000 people in which half are males and half are females, find (any) person who is a female. Simple Example II: Given two polynomials P1(x) and P2(x) (in different representations), check if P1(x) = P2(x). Algorithm. 1. loop 10 times: 1.1 randomly pick a person in the list; 1.2 If this is a female, stop; 2. report(fail) randomly pick a person in the list is implemented as: 1.1.1 r = (rand() % 60,000) + 1; 1.1.2 pick the r-th person in the list;

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance. Computers cannot produce true randomness, but can give pseudo-randomness that is good enough for most applications. in C++, rand() % 100 will give you a random integer r (uniformly) between 0 and 99. Simple Example I: In a list of 60,000 people in which half are males and half are females, find (any) person who is a female. Simple Example II: Given two polynomials P1(x) and P2(x) (in different representations), check if P1(x) = P2(x). Algorithm. 1. loop 10 times: 1.1 randomly pick a person in the list; 1.2 If this is a female, stop; 2. report(fail) Algorithm. 1. x0 = rand(); 2. If (P1(x0) == P2(x0)) then return ( equal ) else return ( not equal ). randomly pick a person in the list is implemented as: 1.1.1 r = (rand() % 60,000) + 1; 1.1.2 pick the r-th person in the list;

Randomized Algorithms A randomized algorithm can use randomness , in the hope of achieving good/better performance. Computers cannot produce true randomness, but can give pseudo-randomness that is good enough for most applications. in C++, rand() % 100 will give you a random integer r (uniformly) between 0 and 99. Simple Example I: In a list of 60,000 people in which half are males and half are females, find (any) person who is a female. Simple Example II: Given two polynomials P1(x) and P2(x) (in different representations), check if P1(x) = P2(x). Algorithm. 1. loop 10 times: 1.1 randomly pick a person in the list; 1.2 If this is a female, stop; 2. report(fail) Algorithm. 1. x0 = rand(); 2. If (P1(x0) == P2(x0)) then return ( equal ) else return ( not equal ). randomly pick a person in the list is implemented as: 1.1.1 r = (rand() % 60,000) + 1; 1.1.2 pick the r-th person in the list; rand() gives an integer r between 0 and 215, which can hardly be the root of P(x) = P1(x) - P2(x) if P1(x) P2(x).

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges.

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges.

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges. Applications: network capacity and reliability.

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges. Applications: network capacity and reliability. Contracting an edge in a graph (shrink the two ends of the edge into a single vertex)

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges. Applications: network capacity and reliability. Contracting an edge in a graph (shrink the two ends of the edge into a single vertex) 1 6 7 4 5 8 2 9 10 3

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges. Applications: network capacity and reliability. Contracting an edge in a graph (shrink the two ends of the edge into a single vertex) 1 6 7 4 5 8 2 9 10 3

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges. Applications: network capacity and reliability. Contracting an edge in a graph (shrink the two ends of the edge into a single vertex) 7 2 1 6 7 8 1,6 4 5 8 2 9 5 3 4 9 10 10 3 Contract edge [1,6]

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges. Applications: network capacity and reliability. Contracting an edge in a graph (shrink the two ends of the edge into a single vertex) 7 2 1 6 7 8 1,6 4 5 8 2 9 5 3 4 9 10 10 3 Contract edge [1,6]

Randomized Algorithms A less simple (but famous) example. Let G be an undirected graph. A cut for G is a set of edges whose removal disconnects the graph. A cut is a min-cut if it contains the fewest edges. Applications: network capacity and reliability. Contracting an edge in a graph (shrink the two ends of the edge into a single vertex) 1 7 6 2 1 6 7 8 1,6 4 5 4 5 8 2 8 2 7,9 9 5 3 4 10 3 9 10 10 3 Contract edge [1,6] Contract edge [7,9]

Karges Min-Cut Randomized Algorithms Karge s Algorithm Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1.

Karges Min-Cut Randomized Algorithms Karge s Algorithm Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Intuition for Karge s Algorithm Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Intuition for Karge s Algorithm Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Let |C| = k, then every vertex in Gh has degree at least k. Thus, Gh has at least hk/2 edges. The probability that the randomly picked edge is in C is not larger than k/(hk/2) = 2/h, and the probability that the randomly picked edge is not in C is at least 1 2/h. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Let |C| = k, then every vertex in Gh has degree at least k. Thus, Gh has at least hk/2 edges. The probability that the randomly picked edge is in C is not larger than k/(hk/2) = 2/h, and the probability that the randomly picked edge is not in C is at least 1 2/h. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n the probability that C is contained in Gn-2is 1 2/(n-1) Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n the probability that C is contained in Gn-2is 1 2/(n-1) .. the probability that C is contained in Ghis 1 2/(h+1) Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n the probability that C is contained in Gn-2is 1 2/(n-1) .. the probability that C is contained in Ghis 1 2/(h+1) .. the probability that C is contained in G3is 1 2/4 the probability that C is contained in G2is 1 2/3 Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n the probability that C is contained in Gn-2is 1 2/(n-1) .. the probability that C is contained in Ghis 1 2/(h+1) .. Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least the probability that C is contained in G3is 1 2/4 (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) the probability that C is contained in G2is 1 2/3 Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n the probability that C is contained in Gn-2is 1 2/(n-1) .. the probability that C is contained in Ghis 1 2/(h+1) .. Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least the probability that C is contained in G3is 1 2/4 (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) = ? 2 ?* ? 3 ? 1* ? 4 ? 2* ? 5 ? 3* * ? (? 3) ? (? 5)* ? (? 2) ? (? 4)* ? (? 1) ? (? 3) the probability that C is contained in G2is 1 2/3 Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n the probability that C is contained in Gn-2is 1 2/(n-1) .. the probability that C is contained in Ghis 1 2/(h+1) .. Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least the probability that C is contained in G3is 1 2/4 (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) = ? 2 ?* ? 3 ? 1* ? 4 ? 2* ? 5 ? 3* * ? (? 3) ? (? 5)* ? (? 2) ? (? 4)* ? (? 1) ? (? 3) the probability that C is contained in G2is 1 2/3 Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Let C by a min-cut of a graph Gh of h vertices. If we randomly pick an edge from , what is the probability that no edge in C is picked? 1 2/h Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Fix a min-cut C in the input graph G (= Gn). the probability that no edge in C is picked in Gn, i.e., the probability that C is contained in Gn-1is 1 2/n the probability that C is contained in Gn-2is 1 2/(n-1) .. the probability that C is contained in Ghis 1 2/(h+1) .. Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least the probability that C is contained in G3is 1 2/4 (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) = ? 2 ?* ? 3 ? 1* ? 4 ? 2* ? 5 ? 3* * ? (? 3) ? (? 5)* ? (? 2) ? (? 4)* ? (? 1) ? (? 3) the probability that C is contained in G2is 1 2/3 2 = ?(? 1) 2/n2 Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Thus, if we run steps 1.1-1.3 of Karge s algorithm, the probability that the cut z0 in step 1.3 is the min-cut C is at least 2/n2, so the probability that z0 in step 3 is NOT the min-cut C is 1 2/n2. Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) = ? 2 ?* ? 3 ? 1* ? 4 ? 2* ? 5 ? 3* * ? (? 3) ? (? 5)* ? (? 2) ? (? 4)* ? (? 1) ? (? 3) 2 = ?(? 1) 2/n2 Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Thus, if we run steps 1.1-1.3 of Karge s algorithm, the probability that the cut z0 in step 1.3 is the min-cut C is at least 2/n2, so the probability that z0 in step 3 is NOT the min-cut C is 1 2/n2. Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Karge s algorithm runs steps 1.1-1.3 10n2 times. Thus, the probability that none of the z0 s constructed in step 1.3 is the min-cut C is (1 2/n2)10n2 1/e20 0.00000001, (note 1 x e-x, where e = 2.718 ). Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) = ? 2 ?* ? 3 ? 1* ? 4 ? 2* ? 5 ? 3* * ? (? 3) ? (? 5)* ? (? 2) ? (? 4)* ? (? 1) ? (? 3) 2 = ?(? 1) 2/n2 Steps 1.1-1.3 in Karge s Algorithm

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Thus, if we run steps 1.1-1.3 of Karge s algorithm, the probability that the cut z0 in step 1.3 is the min-cut C is at least 2/n2, so the probability that z0 in step 3 is NOT the min-cut C is 1 2/n2. Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Karge s algorithm runs steps 1.1-1.3 10n2 times. Thus, the probability that none of the z0 s constructed in step 1.3 is the min-cut C is (1 2/n2)10n2 1/e20 0.00000001, (note 1 x e-x, where e = 2.718 ). Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) = ? 2 ?* ? 3 ? 1* ? 4 ? 2* ? 5 ? 3* * ? (? 3) ? (? 5)* ? (? 2) ? (? 4)* ? (? 1) ? (? 3) 2 = ?(? 1) 2/n2 Theorem. Karge s algorithm (runs in time O(n4) and) constructs a min-cut of the given graph G with a probability 0.99999999.

Karges Min-Cut Randomized Algorithms Karge s Algorithm Correctness of Karge s Algorithm Thus, if we run steps 1.1-1.3 of Karge s algorithm, the probability that the cut z0 in step 1.3 is the min-cut C is at least 2/n2, so the probability that z0 in step 3 is NOT the min-cut C is 1 2/n2. Algorithm Karge(G). 1. loop 10n2 times: 1.1 Gn = G; 1.2 for (h=n; h>2; h--) 1.2.1 randomly pick an edge e in Gh; 1.2.2 Gh-1 = Gh with e contracted; 1.3 take the edges between the two vertices in G2 to make a cut z0; 2. Pick the smallest z0 in step 1. Karge s algorithm runs steps 1.1-1.3 10n2 times. Thus, the probability that none of the z0 s constructed in step 1.3 is the min-cut C is (1 2/n2)10n2 1/e20 0.00000001, (note 1 x e-x, where e = 2.718 ). Thus, the probability that C is contained in G2, i.e., the probability that C is contained in all Gh is at least (1 2/n)*(1 2/(n-1)) * *(1 2/4)*(1 2/3) = ? 2 ?* ? 3 ? 1* ? 4 ? 2* ? 5 ? 3* * ? (? 3) ? (? 5)* ? (? 2) ? (? 4)* ? (? 1) ? (? 3) 2 = ?(? 1) 2/n2 Theorem. Karge s algorithm (runs in time O(n4) and) constructs a min-cut of the given graph G with a probability 0.99999999. (Remark: extending the idea can improve the time to O(n2log2n).)