en>Llightex: /* top */ added bolding

2014-09-05T21:46:57Z

top: added bolding

90.183.57.98: link

2010-11-30T23:00:24Z

link

New page

[[File:Min cut example.svg|thumb|A graph with two 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 (mathematics)|graph]]. It was invented by [[David Karger]] and first published in 1993.<ref name="karger1993">{{cite conference
|last=Karger
|first=David
|title=Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm
|url=http://people.csail.mit.edu/karger/Papers/mincut.ps
|booktitle=Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms
|date=1993
}}</ref>

The idea of the algorithm is based on the concept of [[Edge contraction|contraction of an edge]] <math>(u, v)</math> in an undirected graph <math>G = (V, E)</math>. Informally speaking, the contraction of an edge merges the nodes <math>u</math> and <math>v</math> into one, reducing the total number of nodes of the graph by one. All other edges connecting either <math>u</math> or <math>v</math> 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 (graph theory)|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 ==
{{main|Minimum cut}}
A ''cut'' <math>(S,T)</math> in an undirected graph <math>G = (V, E)</math> is a partition of the vertices <math>V</math> into two non-empty, disjoint sets <math>S\cup T= V</math>.
The ''cutset'' of a cut consists of the edges <math>\{\, uv \in E \colon u\in S, v\in T\,\}</math> 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,
:: <math>w(S,T) = |\{\, uv \in E \colon u\in S, v\in T\,\}|\,.</math>
There are <math>2^{|V|}</math> ways of choosing for each vertex whether it belongs to <math>S</math> or to <math>T</math>, but two of these choices make <math>S</math> or <math>T</math> empty and do not give rise to cuts. Among the remaining choices, swapping the roles of <math>S</math> and <math>T</math> does not change the cut, so each cut is counted twice; therefore, there are <math>2^{|V|-1}-1</math> distinct cuts.
The ''minimum cut problem'' is to find a cut of smallest size among these cuts.

For weighted graphs with positive edge weights <math>w\colon E\rightarrow \mathbf R^+</math> the weight of the cut is the sum of the weights of edges between vertices in each part
:: <math>w(S,T) = \sum_{uv\in E\colon u\in S, v\in T} w(uv)\,,</math>
which agrees with the unweighted definition for <math>w=1</math>.

A cut is sometimes called a “global cut” to distinguish it from an “<math>s</math>-<math>t</math> cut” for a given pair of vertices, which has the additional requirement that <math>s\in S</math> and <math>t\in T</math>. Every global cut is an <math>s</math>-<math>t</math> cut for some <math>s,t\in V</math>. Thus, the minimum cut problem can be solved in [[polynomial time]] by iterating over all choices of <math>s,t\in V</math> and solving the resulting minimum <math>s</math>-<math>t</math> cut problem using the [[max-flow min-cut theorem]] and a polynomial time algorithm for [[maximum flow]], such as the [[Ford–Fulkerson algorithm]], though this approach is not optimal. There is a deterministic algorithm for the minimum cut problem with running time <math>O(mn+n^2\log n)</math>.<ref name="simplemincut">{{cite doi|10.1145/263867.263872}}</ref>

==Contraction algorithm==

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

[[File:Edge contraction in a multigraph.svg|150px|The marked edge is contracted into a single node.]]

The contraction algorithm repeatedly contracts random edges in the graph, until only two nodes remain, at which point there is only a single cut.

[[File:Single run of Karger’s Mincut algorithm.svg|frame|center|Successful run of Karger’s algorithm on a 10-vertex graph. The minimum cut has size 3.]]

'''procedure''' contract(<math>G=(V,E)</math>):
'''while''' <math>|V| > 2</math>
choose <math>e\in E</math> uniformly at random
<math>G \leftarrow G/e</math>
'''return''' the only cut in <math>G</math>

When the graph is represented using [[adjacency list]]s 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 <math>O(|V|^2)</math>. 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 <math>w(e_i)=\pi(i)</math> according to a random permutation <math>\pi</math>. 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 <math>O(|E|\log |E|)</math>.

[[File:Spanning tree interpretation of Karger’s algorithm.svg|frame|center|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 <math>O(|E|)</math> time and space, or <math>O(|E|\log |E|)</math> time and <math>O(|V|)</math> space, respectively.<ref name=karger1993/>

===Success probability of the contraction algorithm===

In a graph <math>G=(V,E)</math> with <math>n=|V|</math> vertices, the contraction algorithm returns a minimum cut with polynomially small probability <math>\binom{n}{2}^{-1}</math>. Every graph has <math>2^{n-1} -1 </math> cuts,<ref>{{citation
| last1 = Patrignani | first1 = Maurizio
| last2 = Pizzonia | first2 = Maurizio
| editor1-last = Brandstädt | editor1-first = Andreas
| editor2-last = Le | editor2-first = Van Bang
| contribution = The complexity of the matching-cut problem
| doi = 10.1007/3-540-45477-2_26
| location = Berlin
| mr = 1905640
| pages = 284–295
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14ÔÇô16, 2001, Proceedings
| volume = 2204
| year = 2001}}.</ref> among which at most <math>\tbinom{n}{2}</math> 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 <math>\tbinom{n}{2}/( 2^{n-1} -1 )</math>

For instance, the [[cycle graph]] on <math>n</math> vertices has exactly <math>\binom{n}{2}</math> minimum cuts, given by every choice of 2 edges. The contraction procedure finds each of these with equal probability.

To establish the bound on the success probability in general, let <math>C</math> denote the edges of a specific minimum cut of size <math>k</math>. The contraction algorithm returns <math>C</math> if none of the random edges belongs to the cutset of <math>C</math>. In particular, the first edge contraction avoids <math>C</math>, which happens with probability <math>1-k/|E|</math>. The minimum degree of <math>G</math> is at least <math>k</math> (otherwise a minimum degree vertex would induce a smaller cut), so <math>|E|\geq nk/2</math>. Thus, the probability that the contraction algorithm picks an edge from <math>C</math> is
::::<math>\frac{k}{|E|} \leq \frac{k}{nk/2} = \frac{2}{n}.</math>
The probability <math>p_n</math> that the contraction algorithm on an <math>n</math>-vertex graph avoids <math>C</math> satisfies the recurrence <math>p_n \geq \bigl(1- \frac{2}{n}\bigr) p_{n-1}</math>, with <math>p_2 = 1</math>, which can be expanded as
:::<math>
p_n \geq \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}\,.
</math>

===Repeating the contraction algorithm===

[[File:10 repetitions of Karger’s contraction procedure.svg|thumb|10 repetitions of the contraction procedure. The 5th repetition finds the minimum cut of size 3.]]

By repeating the contraction algorithm <math> T = \binom{n}{2}\ln n </math> times with independent random choices and returning the smallest cut, the probability of not finding a minimum cut is
:::<math>
\Bigl[1-\binom{n}{2}^{-1}\Bigr]^T
\leq \frac{1}{e^{\ln n}} = \frac{1}{n}\,.
</math>

The total running time for <math>T</math> repetitions for a graph with <math>n</math> vertices and <math>m</math> edges is <math> O(Tm) = O(n^2 m \log n)</math>.

== Karger–Stein algorithm ==
An extension of Karger’s algorithm due to [[David Karger]] and [[Clifford Stein]] achieves an order of magnitude improvement.<ref name= "faster">{{cite doi|10.1145/234533.234534}}</ref>

The basic idea is to perform the contraction procedure until the graph reaches <math>t</math> vertices.

'''procedure''' contract(<math>G=(V,E)</math>, <math>t</math>):
'''while''' <math>|V| > t</math>
choose <math>e\in E</math> uniformly at random
<math>G \leftarrow G/e</math>
'''return''' <math>G</math>

The probability <math>p_{n,t}</math> that this contraction procedure avoids a specific cut <math>C</math> in an <math>n</math>-vertex graph is
:::<math>
\begin{align}
p_{n,t} &\ge \prod_{i=0}^{n-t-1} \Bigl(1-\frac{2}{n-i}\Bigr) = \binom{t}{2}\bigg/\binom{n}{2}\,.
\end{align}</math>

This expression is <math>\Omega(t^2/n^2)</math> becomes less than <math>\frac{1}{2}</math> around <math> t= \lceil 1 + n/\sqrt 2\rceil</math>.
In particular, the probability that an edge from <math>C</math> 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(<math>G= (V,E)</math>):
'''if''' <math>|V| < 6</math>:
'''return''' mincut(<math>V</math>)
'''else''':
<math>t\leftarrow \lceil 1 + |V|/\sqrt 2\rceil</math>
<math>G_1 \leftarrow </math> contract(<math>G</math>, <math>t</math>)
<math>G_2 \leftarrow </math> contract(<math>G</math>, <math>t</math>)
'''return''' min {fastmincut(<math>G_1</math>), fastmincut(<math>G_2</math>)}

=== Analysis ===

The probability <math>P(n)</math> the algorithm finds a specific cutset <math>C</math> is given by the recurrence relation
:::<math>P(n)= 1-\left(1-\frac{1}{2} P\left(\Bigl\lceil 1 + \frac{n}{\sqrt{2}}\Bigr\rceil \right)\right)^2</math>
with solution <math>P(n) = O\left(\frac{1}{\log n}\right)</math>. The running time of fastmincut satisfies
:::<math>T(n)= 2T\left(\Bigl\lceil 1+\frac{n}{\sqrt{2}}\Bigr\rceil\right)+O(n^2)</math>
with solution <math>T(n)=O(n^2\log n)</math>.
To achieve error probability <math>O(1/n)</math>, the algorithm can be repeated <math>O(\log n/P(n))</math> times, for an overall running time of <math>T(n) \cdot \frac{1}{P(n)} = O(n^2\log ^3 n)</math>. This is an order of magnitude improvement over Karger’s original algorithm.

=== Finding all min-cuts ===
'''Theorem:''' With high probability we can find all min cuts in the running time of <math>O(n^2\ln ^3 n)</math>.

'''Proof:''' Since we know that <math>P(n) = O\left(\frac{1}{\ln n}\right)</math>, therefore after running this algorithm <math>O(\ln ^2 n)</math> times The probability of missing a specific min-cut is
::::<math>\Pr[\text{miss a specific min-cut}] = (1-P(n))^{O(\ln ^2 n)} \le \left(1-\frac{c}{\ln n}\right)^{\frac{3\ln ^2 n}{c}} \le e^{-3\ln n} = \frac{1}{n^3}</math>.
And there are at most <math>\binom{n}{2}</math> min-cuts, hence the probability of missing any min-cut is
:::<math>\Pr[\text{miss any min-cut}] \le \binom{n}{2} \cdot \frac{1}{n^3} = O\left(\frac{1}{n}\right).</math>
The probability of failures is considerably small when ''n'' is large enough.∎

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

==References==
<references/>

[[Category:Graph algorithms]]
[[Category:Graph connectivity]]

Minimax eversion - Revision history

en>Llightex: /* top */ added bolding

90.183.57.98: link