Karger's algorithm

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) in an undirected graph G = (V, E) . Informally, the contraction of an edge merges the nodes u and v into one, reducing the total number of nodes of the graph by one. All other edges connecting either u or 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.

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) in an undirected graph G = (V, E) . Informally, the contraction of an edge merges the nodes u and v into one, reducing the total number of nodes of the graph by one. All other edges connecting either u or 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. A cut (S,T) in an undirected graph G = (V, E) is a partition of the vertices V into two non-empty, disjoint sets S\cup T= V . The cutset of a cut consists of the edges \{\, 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) = |\{\, uv \in E \colon u\in S, v\in T\,\}|\,. There are 2^ ways of choosing for each vertex whether it belongs to S or to T , but two of these choices make S or T empty and do not give rise to cuts. Among the remaining choices, swapping the roles of S and T does not change the cut, so each cut is counted twice; therefore, there are 2^ \leqslant \frac{k}{nk/2} = \frac{2}{n}. The probability p_n that the contraction algorithm on an n -vertex graph avoids C satisfies the recurrence p_n \geqslant \left( 1 - \frac{2}{n} \right) p_{n-1} , with p_2 = 1 , which can be expanded as p_n \geqslant \prod_{i=0}^{n-3} \Bigl(1-\frac{2}{n-i}\Bigr) = \prod_{i=0}^{n-3} {\frac{n-i-2}{n-i}} ===Repeating the contraction algorithm=== By repeating the contraction algorithm 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 \left[1-\binom{n}{2}^{-1}\right]^T \leq \frac{1}{e^{\ln n}} = \frac{1}{n}\,. The total running time for T repetitions for a graph with n vertices and m edges is O(Tm) = O(n^2 m \log n) . procedure contract( G=(V,E) , t ): while |V| > t choose e\in E uniformly at random G \leftarrow G/e return G The probability p_{n,t} that this contraction procedure avoids a specific cut C in an n -vertex graph is p_{n,t} \ge \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 and becomes less than \frac{1}{2} around t= n/\sqrt 2 . In particular, the probability that an edge from 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) ): if |V| \le 6 : return contract( G , 2 ) else: t\leftarrow \lceil 1 + |V|/\sqrt 2\rceil G_1 \leftarrow contract( G , t ) G_2 \leftarrow contract( G , t ) return min{fastmincut( G_1 ), fastmincut( G_2 )} P(n)= 1-\left(1-\frac{1}{2} P\left(\Bigl\lceil 1 + \frac{n}{\sqrt{2}}\Bigr\rceil \right)\right)^2 with solution P(n) = \Omega\left(\frac{1}{\log n}\right) . The running time of fastmincut satisfies T(n)= 2T\left(\Bigl\lceil 1+\frac{n}{\sqrt{2}}\Bigr\rceil\right)+O(n^2) with solution T(n)=O(n^2\log n) . To achieve error probability O(1/n) , the algorithm can be repeated O(\log n/P(n)) times, for an overall running time of 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. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1352634526 under CC BY-SA 4.0; modifications have been made.