Karger's algorithm#Karger–Stein algorithm

{{main|Minimum cut}}

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\backslash cup\; T=\; V$. The cutset of a cut consists of the edges $\backslash \{\backslash ,\; uv\; \backslash in\; E\; \backslash colon\; u\backslash in\; S,\; v\backslash in\; T\backslash ,\backslash \}$ 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)\; =\; |\backslash \{\backslash ,\; uv\; \backslash in\; E\; \backslash colon\; u\backslash in\; S,\; v\backslash in\; T\backslash ,\backslash \}|\backslash ,.$

There are $2^$

The minimum cut problem is to find a cut of smallest size among these cuts.

For weighted graphs with positive edge weights $w\backslash colon\; E\backslash rightarrow\; \backslash mathbf\; R^+$ the weight of the cut is the sum of the weights of edges between vertices in each part

:: $w(S,T)\; =\; \backslash sum\_\{uv\backslash in\; E\backslash colon\; u\backslash in\; S,\; v\backslash in\; T\}\; w(uv)\backslash ,,$

which agrees with the unweighted definition for $w=1$.

A cut is sometimes called a “global cut” to distinguish it from an “$s$-$t$ cut” for a given pair of vertices, which has the additional requirement that $s\backslash in\; S$ and $t\backslash in\; T$. Every global cut is an $s$-$t$ cut for some $s,t\backslash in\; V$. Thus, the minimum cut problem can be solved in polynomial time by iterating over all choices of $s,t\backslash in\; V$ and solving the resulting minimum $s$-$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(mn+n^2\backslash log\; n)$.{{Cite journal | last1 = Stoer | first1 = M. | last2 = Wagner | first2 = F. | doi = 10.1145/263867.263872 | title = A simple min-cut algorithm | journal = Journal of the ACM | volume = 44 | issue = 4 | pages = 585 | year = 1997 | s2cid = 15220291 | doi-access = free }}

The fundamental operation of Karger’s algorithm is a form of edge contraction. The result of contracting the edge $e=\backslash \{u,v\backslash \}$ is a new node $uv$. Every edge $\backslash \{w,u\backslash \}$ or $\backslash \{w,v\backslash \}$ for $w\backslash notin\backslash \{u,v\backslash \}$ to the endpoints of the contracted edge is replaced by an edge $\backslash \{w,uv\backslash \}$ to the new node. Finally, the contracted nodes $u$ and $v$ with all their incident edges are removed. In particular, the resulting graph contains no self-loops. The result of contracting edge $e$ is denoted $G/e$.

File:Edge contraction in a multigraph.svg

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.

File:Single run of Karger’s Mincut algorithm.svg

procedure contract($G=(V,E)$):

while $|V|\; >\; 2$

choose $e\backslash in\; E$ uniformly at random

$G\; \backslash leftarrow\; G/e$

return the only cut in $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)$. 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)=\backslash pi(i)$ according to a random permutation $\backslash 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|\backslash log\; |E|)$.

File:Spanning tree interpretation of Karger’s algorithm.svg

The best known implementations use $O(|E|)$ time and space, or $O(|E|\backslash log\; |E|)$ time and $O(|V|)$ space, respectively.

In a graph $G=(V,E)$ with $n=|V|$ vertices, the contraction algorithm returns a minimum cut with polynomially small probability $\backslash binom\{n\}\{2\}^\{-1\}$. Recall that every graph has $2^\{n-1\}\; -1$ cuts (by the discussion in the previous section), among which at most $\backslash 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 $\backslash frac\{\backslash tbinom\{n\}\{2\}\}\{2^\{n-1\}\; -1\}$.

For instance, the cycle graph on $n$ vertices has exactly $\backslash 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$ denote the edges of a specific minimum cut of size $k$. The contraction algorithm returns $C$ if none of the random edges deleted by the algorithm belongs to the cutset $C$. In particular, the first edge contraction avoids $C$, which happens with probability $1-k/|E|$. The minimum degree of $G$ is at least $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|\backslash geqslant\; nk/2$. Thus, the probability that the contraction algorithm picks an edge from $C$ is

::::$\backslash frac\{k\}$

The probability $p\_n$ that the contraction algorithm on an $n$-vertex graph avoids $C$ satisfies the recurrence $p\_n\; \backslash geqslant\; \backslash left(\; 1\; -\; \backslash frac\{2\}\{n\}\; \backslash 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}}

= \frac{n-2}{n}\cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2}\cdots \frac{3}{5}\cdot \frac{2}{4} \cdot \frac{1}{3}

= \binom{n}{2}^{-1}\,.

File:10 repetitions of Karger’s contraction procedure.svg

By repeating the contraction algorithm $T\; =\; \backslash binom\{n\}\{2\}\backslash 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\; \backslash log\; n)$.

An extension of Karger’s algorithm due to David Karger and Clifford Stein achieves an order of magnitude improvement.{{Cite journal | last1 = Karger | first1 = David R. | author-link1 = David Karger| last2 = Stein | first2 = Clifford| author-link2 = Clifford Stein | doi = 10.1145/234533.234534 | title = A new approach to the minimum cut problem | journal = Journal of the ACM | volume = 43 | issue = 4 | pages = 601 | year = 1996 | s2cid = 5385337 | url = http://www.columbia.edu/~cs2035/courses/ieor6614.S09/Contraction.pdf}}

The basic idea is to perform the contraction procedure until the graph reaches $t$ vertices.

procedure contract($G=(V,E)$, $t$):

while $|V|\; >\; t$

choose $e\backslash in\; E$ uniformly at random

$G\; \backslash 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 $\backslash frac\{1\}\{2\}$ around $t=\; n/\backslash 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|\; \backslash le\; 6$:

return contract($G$, $2$)

else:

$t\backslash leftarrow\; \backslash lceil\; 1\; +\; |V|/\backslash sqrt\; 2\backslash rceil$

$G\_1\; \backslash leftarrow$ contract($G$, $t$)

$G\_2\; \backslash leftarrow$ contract($G$, $t$)

return min{fastmincut($G\_1$), fastmincut($G\_2$)}

The contraction parameter $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$). 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.

The probability $P(n)$ that this random tree of successful calls contains a long-enough path to reach the base of the recursion and find $C$ is given by the recurrence relation

:::$P(n)=\; 1-\backslash left(1-\backslash frac\{1\}\{2\}\; P\backslash left(\backslash Bigl\backslash lceil\; 1\; +\; \backslash frac\{n\}\{\backslash sqrt\{2\}\}\backslash Bigr\backslash rceil\; \backslash right)\backslash right)^2$

with solution $P(n)\; =\; \backslash Omega\backslash left(\backslash frac\{1\}\{\backslash log\; n\}\backslash right)$. The running time of fastmincut satisfies

:::$T(n)=\; 2T\backslash left(\backslash Bigl\backslash lceil\; 1+\backslash frac\{n\}\{\backslash sqrt\{2\}\}\backslash Bigr\backslash rceil\backslash right)+O(n^2)$

with solution $T(n)=O(n^2\backslash log\; n)$. To achieve error probability $O(1/n)$, the algorithm can be repeated $O(\backslash log\; n/P(n))$ times, for an overall running time of $T(n)\; \backslash cdot\; \backslash frac\{\backslash log\; n\}\{P(n)\}\; =\; O(n^2\backslash log\; ^3\; n)$. This is an order of magnitude improvement over Karger’s original algorithm.

To determine a min-cut, one has to touch every edge in the graph at least once, which is $\backslash Theta(n^2)$ time in a dense graph. The Karger–Stein's min-cut algorithm takes the running time of $O(n^2\backslash ln\; ^\{O(1)\}\; n)$, which is very close to that.

Category:Graph algorithms

Category:Graph connectivity