In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993. The idea of the algorithm is based on the concept of contraction of an edge ( u , v ) {\displaystyle (u,v)} in an undirected graph G = ( V , E ) {\displaystyle G=(V,E)} . Informally, the contraction of an edge merges the nodes u {\displaystyle u} and v {\displaystyle v} into one, reducing the total number of nodes of the graph by one. All other edges connecting either u {\displaystyle u} or v {\displaystyle v} are "reattached" to the merged node, effectively producing a multigraph. Karger's basic algorithm iteratively contracts randomly chosen edges until only two nodes remain; those nodes represent a cut in the original graph. By iterating this basic algorithm a sufficient number of times, a minimum cut can be found with high probability.
The global minimum cut problem
A cut ( S , T ) {\displaystyle (S,T)} in an undirected graph G = ( V , E ) {\displaystyle G=(V,E)} is a partition of the vertices V {\displaystyle V} into two non-empty, disjoint sets S ∪ T = V {\displaystyle S\cup T=V} . The cutset of a cut consists of the edges { u v ∈ E : u ∈ S , v ∈ T } {\displaystyle \{\,uv\in E\colon u\in S,v\in T\,\}} between the two parts. The size (or weight) of a cut in an unweighted graph is the cardinality of the cutset, i.e., the number of edges between the two parts,
w ( S , T ) = | { u v ∈ E : u ∈ S , v ∈ T } | . {\displaystyle w(S,T)=|\{\,uv\in E\colon u\in S,v\in T\,\}|\,.}
There are 2 | V | {\displaystyle 2^{|V|}} ways of choosing for each vertex whether it belongs to S {\displaystyle S} or to T {\displaystyle T} , but two of these choices make S {\displaystyle S} or T {\displaystyle T} empty and do not give rise to cuts. Among the remaining choices, swapping the roles of S {\displaystyle S} and T {\displaystyle T} does not change the cut, so each cut is counted twice; therefore, there are 2 | V | − 1 − 1 {\displaystyle 2^{|V|-1}-1} distinct cuts. The minimum cut problem is to find a cut of smallest size among these cuts. For weighted graphs with positive edge weights w : E → R + {\displaystyle w\colon E\rightarrow \mathbf {R} ^{+}} the weight of the cut is the sum of the weights of edges between vertices in each part
w ( S , T ) = ∑ u v ∈ E : u ∈ S , v ∈ T w ( u v ) , {\displaystyle w(S,T)=\sum _{uv\in E\colon u\in S,v\in T}w(uv)\,,}
which agrees with the unweighted definition for w = 1 {\displaystyle w=1} . A cut is sometimes called a “global cut” to distinguish it from an “ s {\displaystyle s} - t {\displaystyle t} cut” for a given pair of vertices, which has the additional requirement that s ∈ S {\displaystyle s\in S} and t ∈ T {\displaystyle t\in T} . Every global cut is an s {\displaystyle s} - t {\displaystyle t} cut for some s , t ∈ V {\displaystyle s,t\in V} . Thus, the minimum cut problem can be solved in polynomial time by iterating over all choices of s , t ∈ V {\displaystyle s,t\in V} and solving the resulting minimum s {\displaystyle s} - t {\displaystyle t} cut problem using the max-flow min-cut theorem and a polynomial time algorithm for maximum flow, such as the push-relabel algorithm, though this approach is not optimal. Better deterministic algorithms for the global minimum cut problem include the Stoer–Wagner algorithm, which has a running time of O ( m n + n 2 log n ) {\displaystyle O(mn+n^{2}\log n)} .
… excerpt ends here. Continue reading the full article.
