From Wikipedia, the free encyclopedia
Randomized algorithm for minimum cuts
A graph and two of its cuts. The dotted line in red is a cut with three crossing edges. The dashed line in green is a min-cut of this graph, crossing only two edges.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.[1]
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 speaking, 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[edit]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,
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
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)} .[2]
Contraction algorithm[edit]The fundamental operation of Karger’s algorithm is a form of edge contraction. The result of contracting the edge e = { u , v } {\displaystyle e=\{u,v\}} is a new node u v {\displaystyle uv} . Every edge { w , u } {\displaystyle \{w,u\}} or { w , v } {\displaystyle \{w,v\}} for w ∉ { u , v } {\displaystyle w\notin \{u,v\}} to the endpoints of the contracted edge is replaced by an edge { w , u v } {\displaystyle \{w,uv\}} to the new node. Finally, the contracted nodes u {\displaystyle u} and v {\displaystyle v} with all their incident edges are removed. In particular, the resulting graph contains no self-loops. The result of contracting edge e {\displaystyle e} is denoted G / e {\displaystyle G/e} .
The contraction algorithm repeatedly contracts random edges in the graph, until only two nodes remain, at which point there is only a single cut.
The key idea of the algorithm is that it is far more likely for non min-cut edges than min-cut edges to be randomly selected and lost to contraction, since min-cut edges are usually vastly outnumbered by non min-cut edges. Subsequently, it is plausible that the min-cut edges will survive all the edge contraction, and the algorithm will correctly identify the min-cut edge.
Successful run of Karger’s algorithm on a 10-vertex graph. The minimum cut has size 3.
procedure contract(
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
):
while
|
V
|
>
2
{\displaystyle |V|>2}
choose
e
∈
E
{\displaystyle e\in E}
uniformly at random
G
←
G
/
e
{\displaystyle G\leftarrow G/e}
return the only cut in
G
{\displaystyle G}
When the graph is represented using adjacency lists or an adjacency matrix, a single edge contraction operation can be implemented with a linear number of updates to the data structure, for a total running time of O ( | V | 2 ) {\displaystyle O(|V|^{2})} . Alternatively, the procedure can be viewed as an execution of Kruskal’s algorithm for constructing the minimum spanning tree in a graph where the edges have weights w ( e i ) = π ( i ) {\displaystyle w(e_{i})=\pi (i)} according to a random permutation π {\displaystyle \pi } . Removing the heaviest edge of this tree results in two components that describe a cut. In this way, the contraction procedure can be implemented like Kruskal’s algorithm in time O ( | E | log | E | ) {\displaystyle O(|E|\log |E|)} .
The random edge choices in Karger’s algorithm correspond to an execution of Kruskal’s algorithm on a graph with random edge ranks until only two components remain.The best known implementations use O ( | E | ) {\displaystyle O(|E|)} time and space, or O ( | E | log | E | ) {\displaystyle O(|E|\log |E|)} time and O ( | V | ) {\displaystyle O(|V|)} space, respectively.[1]
Success probability of the contraction algorithm[edit]In a graph G = ( V , E ) {\displaystyle G=(V,E)} with n = | V | {\displaystyle n=|V|} vertices, the contraction algorithm returns a minimum cut with polynomially small probability ( n 2 ) − 1 {\displaystyle {\binom {n}{2}}^{-1}} . Recall that every graph has 2 n − 1 − 1 {\displaystyle 2^{n-1}-1} cuts (by the discussion in the previous section), among which at most ( n 2 ) {\displaystyle {\tbinom {n}{2}}} can be minimum cuts. Therefore, the success probability for this algorithm is much better than the probability for picking a cut at random, which is at most ( n 2 ) 2 n − 1 − 1 {\displaystyle {\frac {\tbinom {n}{2}}{2^{n-1}-1}}} .
For instance, the cycle graph on n {\displaystyle n} vertices has exactly ( n 2 ) {\displaystyle {\binom {n}{2}}} minimum cuts, given by every choice of 2 edges. The contraction procedure finds each of these with equal probability.
To further establish the lower bound on the success probability, let C {\displaystyle C} denote the edges of a specific minimum cut of size k {\displaystyle k} . The contraction algorithm returns C {\displaystyle C} if none of the random edges deleted by the algorithm belongs to the cutset C {\displaystyle C} . In particular, the first edge contraction avoids C {\displaystyle C} , which happens with probability 1 − k / | E | {\displaystyle 1-k/|E|} . The minimum degree of G {\displaystyle G} is at least k {\displaystyle k} (otherwise a minimum degree vertex would induce a smaller cut where one of the two partitions contains only the minimum degree vertex), so | E | ⩾ n k / 2 {\displaystyle |E|\geqslant nk/2} . Thus, the probability that the contraction algorithm picks an edge from C {\displaystyle C} is
The probability p n {\displaystyle p_{n}} that the contraction algorithm on an n {\displaystyle n} -vertex graph avoids C {\displaystyle C} satisfies the recurrence p n ⩾ ( 1 − 2 n ) p n − 1 {\displaystyle p_{n}\geqslant \left(1-{\frac {2}{n}}\right)p_{n-1}} , with p 2 = 1 {\displaystyle p_{2}=1} , which can be expanded as
By repeating the contraction algorithm T = ( n 2 ) ln n {\displaystyle T={\binom {n}{2}}\ln n} times with independent random choices and returning the smallest cut, the probability of not finding a minimum cut is
The total running time for T {\displaystyle T} repetitions for a graph with n {\displaystyle n} vertices and m {\displaystyle m} edges is O ( T m ) = O ( n 2 m log n ) {\displaystyle O(Tm)=O(n^{2}m\log n)} .
Karger–Stein algorithm[edit]An extension of Karger’s algorithm due to David Karger and Clifford Stein achieves an order of magnitude improvement.[3]
The basic idea is to perform the contraction procedure until the graph reaches t {\displaystyle t} vertices.
procedure contract(
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
,
t
{\displaystyle t}
):
while
|
V
|
>
t
{\displaystyle |V|>t}
choose
e
∈
E
{\displaystyle e\in E}
uniformly at random
G
←
G
/
e
{\displaystyle G\leftarrow G/e}
return
G
{\displaystyle G}
The probability p n , t {\displaystyle p_{n,t}} that this contraction procedure avoids a specific cut C {\displaystyle C} in an n {\displaystyle n} -vertex graph is
p n , t ≥ ∏ i = 0 n − t − 1 ( 1 − 2 n − i ) = ( t 2 ) / ( n 2 ) . {\displaystyle p_{n,t}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}
This expression is approximately t 2 / n 2 {\displaystyle t^{2}/n^{2}} and becomes less than 1 2 {\displaystyle {\frac {1}{2}}} around t = n / 2 {\displaystyle t=n/{\sqrt {2}}} . In particular, the probability that an edge from C {\displaystyle C} is contracted grows towards the end. This motivates the idea of switching to a slower algorithm after a certain number of contraction steps.
procedure fastmincut(
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
):
if
|
V
|
≤
6
{\displaystyle |V|\leq 6}
:
return contract(
G
{\displaystyle G}
,
2
{\displaystyle 2}
)
else:
t
←
⌈
1
+
|
V
|
/
2
⌉
{\displaystyle t\leftarrow \lceil 1+|V|/{\sqrt {2}}\rceil }
G
1
←
{\displaystyle G_{1}\leftarrow }
contract(
G
{\displaystyle G}
,
t
{\displaystyle t}
)
G
2
←
{\displaystyle G_{2}\leftarrow }
contract(
G
{\displaystyle G}
,
t
{\displaystyle t}
)
return min{fastmincut(
G
1
{\displaystyle G_{1}}
), fastmincut(
G
2
{\displaystyle G_{2}}
)}
The contraction parameter t {\displaystyle t} is chosen so that each call to contract has probability at least 1/2 of success (that is, of avoiding the contraction of an edge from a specific cutset C {\displaystyle C} ). This allows the successful part of the recursion tree to be modeled as a random binary tree generated by a critical Galton–Watson process, and to be analyzed accordingly.[3]
The probability P ( n ) {\displaystyle P(n)} that this random tree of successful calls contains a long-enough path to reach the base of the recursion and find C {\displaystyle C} is given by the recurrence relation
with solution P ( n ) = Ω ( 1 log n ) {\displaystyle P(n)=\Omega \left({\frac {1}{\log n}}\right)} . The running time of fastmincut satisfies
with solution T ( n ) = O ( n 2 log n ) {\displaystyle T(n)=O(n^{2}\log n)} . To achieve error probability O ( 1 / n ) {\displaystyle O(1/n)} , the algorithm can be repeated O ( log n / P ( n ) ) {\displaystyle O(\log n/P(n))} times, for an overall running time of T ( n ) ⋅ log n P ( n ) = O ( n 2 log 3 n ) {\displaystyle T(n)\cdot {\frac {\log n}{P(n)}}=O(n^{2}\log ^{3}n)} . This is an order of magnitude improvement over Karger’s original algorithm.[3]
To determine a min-cut, one has to touch every edge in the graph at least once, which is Θ ( n 2 ) {\displaystyle \Theta (n^{2})} time in a dense graph. The Karger–Stein's min-cut algorithm takes the running time of O ( n 2 ln O ( 1 ) n ) {\displaystyle O(n^{2}\ln ^{O(1)}n)} , which is very close to that.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4