概率论与数理统计 (Spring 2023)/Karger's min-cut algorithm: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
No edit summary
 
(18 intermediate revisions by the same user not shown)
Line 1: Line 1:
= Graph Cut =
Let <math>G(V, E)</math> be an undirected graph. A subset <math>C\subseteq E</math> of edges is a '''cut''' of graph <math>G</math> if <math>G</math> becomes ''disconnected'' after deleting all edges in <math>C</math>.  
Let <math>G(V, E)</math> be an undirected graph. A subset <math>C\subseteq E</math> of edges is a '''cut''' of graph <math>G</math> if <math>G</math> becomes ''disconnected'' after deleting all edges in <math>C</math>.  


Line 7: Line 6:
:<math>E(S,T)=\{uv\in E\mid u\in S, v\in T\}</math>.
:<math>E(S,T)=\{uv\in E\mid u\in S, v\in T\}</math>.


Given a graph <math>G</math>, there might be many cuts in <math>G</math>, and we are interested in finding the '''minimum''' or '''maximum''' cut.
= Min-Cut =
The '''min-cut problem''', also called the '''global minimum cut problem''', is defined as follows.
The '''min-cut problem''', also called the '''global minimum cut problem''', is defined as follows.
{{Theorem|Min-cut problem|
{{Theorem|Min-cut problem|
Line 20: Line 16:
We consider the problem in a slightly more generalized setting, where the input graphs <math>G</math> can be '''multi-graphs''', meaning that there could be multiple '''parallel edges''' between two vertices <math>u</math> and <math>v</math>. The cuts in multi-graphs are defined in the same way as before, and the cost of a cut <math>C</math> is given by the total number of edges (including parallel edges) in <math>C</math>. Equivalently, one may think of a multi-graph as a graph with integer edge weights, and the cost of a cut <math>C</math> is the total weights of all edges in <math>C</math>.
We consider the problem in a slightly more generalized setting, where the input graphs <math>G</math> can be '''multi-graphs''', meaning that there could be multiple '''parallel edges''' between two vertices <math>u</math> and <math>v</math>. The cuts in multi-graphs are defined in the same way as before, and the cost of a cut <math>C</math> is given by the total number of edges (including parallel edges) in <math>C</math>. Equivalently, one may think of a multi-graph as a graph with integer edge weights, and the cost of a cut <math>C</math> is the total weights of all edges in <math>C</math>.


A canonical deterministic algorithm for this problem is through the [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem max-flow min-cut theorem]. The max-flow algorithm finds us a minimum '''<math>s</math>-<math>t</math> cut''', which disconnects a '''source''' <math>s\in V</math> from a '''sink''' <math>t\in V</math>, both specified as part of the input. A global min cut can be found by exhaustively finding the minimum <math>s</math>-<math>t</math> cut for an arbitrarily fixed source <math>s</math> and all possible sink <math>t\neq s</math>. This takes <math>(n-1)\times</math>max-flow time where <math>n=|V|</math> is the number of vertices.
A canonical deterministic algorithm for this problem is through the [http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem max-flow min-cut theorem]. The max-flow algorithm finds us a minimum '''<math>s</math>-<math>t</math> cut''', which disconnects a '''source''' <math>s\in V</math> from a '''sink''' <math>t\in V</math>, both specified as part of the input. A global min cut can be found by exhaustively finding the minimum <math>s</math>-<math>t</math> cut for an arbitrarily fixed source <math>s</math> and all possible sink <math>t\neq s</math>.  
 
The fastest known deterministic algorithm for the minimum cut problem on multi-graphs is the [https://en.wikipedia.org/wiki/Stoer–Wagner_algorithm Stoer–Wagner algorithm], which achieves an <math>O(mn+n^2\log n)</math> time complexity where <math>m=|E|</math> is the total number of edges (counting the parallel edges).
 
If we restrict the input to be '''simple graphs''' (meaning there is no parallel edges) with no edge weight, there are better algorithms. A deterministic algorithm of [https://dl.acm.org/citation.cfm?id=2746588 Ken-ichi Kawarabayashi and Mikkel Thorup] published in STOC 2015, achieves the near-linear (in the number of edges) time complexity.


== Karger's ''Contraction'' algorithm ==
== Karger's Algorithm ==
We will describe a simple and elegant randomized algorithm for the min-cut problem. The algorithm is due to [http://people.csail.mit.edu/karger/ David Karger].
We will describe a simple and elegant randomized algorithm for the min-cut problem. The algorithm is due to [http://people.csail.mit.edu/karger/ David Karger].


Line 58: Line 50:
}}
}}


Another way of looking at the contraction operator Contract(<math>G</math>,<math>e</math>) is that we are dealing with classes of vertices. Let <math>V=\{v_1,v_2,\ldots,v_n\}</math> be the set of all vertices. We start with <math>n</math> vertex classes <math>S_1,S_2,\ldots, S_n</math> with each class <math>S_i=\{v_i\}</math> contains one vertex. By calling <math>Contract(G,uv)</math>, where <math>u\in S_i</math> and <math>v\in S_j</math> for distinct <math>i\neq j</math>, we take union of <math>S_i</math> and <math>S_j</math>. The edges in the contracted multi-graph are the edges that cross between different vertex classes.
Another way of looking at the contraction operator Contract(<math>G</math>,<math>e</math>) is that it unions two classes of vertices. Let <math>V=\{v_1,v_2,\ldots,v_n\}</math> be the set of all vertices. We start with <math>n</math> vertex classes <math>S_1,S_2,\ldots, S_n</math> with each class <math>S_i=\{v_i\}</math> contains one vertex. By calling <math>Contract(G,uv)</math>, where <math>u\in S_i</math> and <math>v\in S_j</math> for distinct <math>i\neq j</math>, we take union of <math>S_i</math> and <math>S_j</math>. The edges in the contracted multi-graph are the edges that cross between different vertex classes.


This view of contraction is illustrated by the following picture:
This view of contraction is illustrated by the following picture:
[[Image:Contract_class.png|600px|center]]
[[Image:Contract_class.png|600px|center]]


The following claim is left as an exercise for the class:
== Analysis of Karger's Algorithm ==
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
We now analyze the above algorithm. Since the algorithm is '''''randomized''''', its output cut is random even when the input is fixed, so ''the output may not always be correct''. We want to give a theoretical guarantee of the chance that the algorithm returns a correct answer on an arbitrary input.
|
*With suitable choice of data structures, each operation <math>Contract(G,e)</math> can be implemented within running time <math>O(n)</math> where <math>n=|V|</math> is the number of vertices.
|}
 
In the above '''''RandomContract''''' algorithm, there are precisely <math>n-2</math> contractions. Therefore, we have the following time upper bound.
{{Theorem|Theorem|
: For any multigraph with <math>n</math> vertices, the running time of the '''''RandomContract''''' algorithm is <math>O(n^2)</math>.
}}
We emphasize that it's the time complexity of a "single running" of the algorithm: later we will see we may need to run this algorithm for many times to guarantee a desirable accuracy.
 
== Analysis of accuracy ==
We now analyze the performance of the above algorithm. Since the algorithm is '''''randomized''''', its output cut is a random variable even when the input is fixed, so ''the output may not always be correct''. We want to give a theoretical guarantee of the chance that the algorithm returns a correct answer on an arbitrary input.


More precisely, on an arbitrarily fixed input multi-graph <math>G</math>, we want to answer the following question rigorously:
More precisely, on an arbitrarily fixed input multi-graph <math>G</math>, we want to answer the following question rigorously:
Line 86: Line 66:
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
|
*In above argument we use the simple law in probability that <math>\Pr[A]\le \Pr[B]</math> if <math>A\subseteq B</math>, i.e. event <math>A</math> implies event <math>B</math>.
*In above argument we use the simple law in probability that <math>\Pr(A)\le \Pr(B)</math> if <math>A\subseteq B</math>, i.e. event <math>A</math> implies event <math>B</math>.
|}
|}


Line 92: Line 72:
*Let <math>e_1,e_2,\ldots,e_{n-2}</math> denote the sequence of random edges chosen to contract in a running of ''RandomContract'' algorithm.  
*Let <math>e_1,e_2,\ldots,e_{n-2}</math> denote the sequence of random edges chosen to contract in a running of ''RandomContract'' algorithm.  
*Let <math>G_1=G</math> denote the original input multi-graph. And for <math>i=1,2,\ldots,n-2</math>, let <math>G_{i+1}=Contract(G_{i},e_i)</math> be the multigraph after <math>i</math>th contraction.
*Let <math>G_1=G</math> denote the original input multi-graph. And for <math>i=1,2,\ldots,n-2</math>, let <math>G_{i+1}=Contract(G_{i},e_i)</math> be the multigraph after <math>i</math>th contraction.
Obviously <math>e_1,e_2,\ldots,e_{n-2}</math> are random variables, and they are the ''only'' random choices used in the algorithm: meaning that they along with the input <math>G</math>, uniquely determine the sequence of multi-graphs <math>G_1,G_2,\ldots,G_{n-2}</math> in every iteration as well as the final output.  
Obviously <math>e_1,e_2,\ldots,e_{n-2}</math> are random, and they are the ''only'' random choices used in the algorithm: meaning that they along with the input <math>G</math>, uniquely determine the sequence of multi-graphs <math>G_1,G_2,\ldots,G_{n-2}</math> in every iteration as well as the final output.  


We now compute the probability <math>p_C</math> by decompose it into more elementary events involving <math>e_1,e_2,\ldots,e_{n-2}</math>. This is due to the following proposition.
We now compute the probability <math>p_C</math> by decompose it into more elementary events involving <math>e_1,e_2,\ldots,e_{n-2}</math>. This is due to the following proposition.
Line 104: Line 84:
We then observe that a cut <math>C</math> in <math>G</math> "survives" in the contracted graph <math>G'</math> if and only if the contracted edge <math>e\not\in C</math>.
We then observe that a cut <math>C</math> in <math>G</math> "survives" in the contracted graph <math>G'</math> if and only if the contracted edge <math>e\not\in C</math>.


Both observations are easy to verify by the definition of contraction operator (in particular, easier to verify if we take the vertex class interpretation). The detailed proofs are left as an exercise.
Both observations are easy to verify by the definition of contraction operator (in particular, easier to verify if we take the vertex class interpretation).
}}
}}


Line 121: Line 101:
\end{align}
\end{align}
</math>
</math>
The last equation is due to the so called '''chain rule''' in probability.
The last equation is due to the '''chain rule'''.
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
*The '''chain rule''', also known as the '''law of progressive conditioning''', is the following proposition: for a sequence of events (not necessarily independent) <math>A_1,A_2,\ldots,A_n</math>,
::<math>\Pr[\forall i, A_i]=\prod_{i=1}^n\Pr[A_i\mid \forall j<i, A_j]</math>.
:It is a simple consequence of the definition of conditional probability. By definition of conditional probability,
::<math>\Pr[A_n\mid \forall j<n]=\frac{\Pr[\forall i, A_i]}{\Pr[\forall j<n, A_j]}</math>,
:and equivalently we have
::<math>\Pr[\forall i, A_i]=\Pr[\forall j<n, A_j]\Pr[A_n\mid \forall j<n]</math>.
:Recursively apply this to <math>\Pr[\forall j<n, A_j]</math> we obtain the chain rule.
|}
 
Back to the analysis of probability <math>p_C</math>.  


Now our task is to give lower bound to each <math>p_i=\Pr[e_i\not\in C\mid \forall j<i, e_j\not\in C]</math>. The condition <math>\mbox{``}\forall j<i, e_j\not\in C\mbox{''}</math> means the min-cut <math>C</math> survives all first <math>i-1</math> contractions <math>e_1,e_2,\ldots,e_{i-1}</math>, which due to Proposition 1 means that <math>C</math> is also a min-cut in the multi-graph <math>G_i</math> obtained from applying the first <math>(i-1)</math> contractions.
Now our task is to give lower bound to each <math>p_i=\Pr[e_i\not\in C\mid \forall j<i, e_j\not\in C]</math>. The condition <math>\mbox{``}\forall j<i, e_j\not\in C\mbox{''}</math> means the min-cut <math>C</math> survives all first <math>i-1</math> contractions <math>e_1,e_2,\ldots,e_{i-1}</math>, which due to Proposition 1 means that <math>C</math> is also a min-cut in the multi-graph <math>G_i</math> obtained from applying the first <math>(i-1)</math> contractions.
Line 181: Line 149:
: For any multigraph with <math>n</math> vertices, the ''RandomContract'' algorithm returns a minimum cut with probability at least <math>\frac{2}{n(n-1)}</math>.
: For any multigraph with <math>n</math> vertices, the ''RandomContract'' algorithm returns a minimum cut with probability at least <math>\frac{2}{n(n-1)}</math>.
}}
}}
At first glance this seems to be a miserable chance of success. However, notice that there may be exponential many cuts in a graph (because potentially every nonempty subset <math>S\subset V</math> corresponds to a cut <math>C=E(S,\overline{S})</math>), and Karger's algorithm effectively reduce this exponential-sized space of feasible solutions to a quadratic size one, an exponential improvement!
At first glance this seems to be a quite slim chance of success. However, notice that there may be exponential many cuts in a graph (because potentially every nonempty subset <math>S\subset V</math> corresponds to a cut <math>C=E(S,\overline{S})</math>), and Karger's algorithm effectively reduce this exponential-sized space to quadratic-sized, an exponential improvement!


We can run ''RandomContract'' independently for <math>t=\frac{n(n-1)\ln n}{2}</math> times and return the smallest cut ever returned. The probability that a minimum cut is found is at least:
We can run ''RandomContract'' independently for <math>t=\left\lceil\frac{n(n-1)\ln n}{2}\right\rceil</math> times and return the smallest cut ever returned. The probability that a minimum cut is found is at least:


:<math>\begin{align}
:<math>\begin{align}
Line 192: Line 160:
\end{align}</math>
\end{align}</math>


Recall that a running of ''RandomContract'' algorithm takes <math>O(n^2)</math> time. Altogether this gives us a randomized algorithm running in time <math>O(n^4\log n)</math> and find a minimum cut [https://en.wikipedia.org/wiki/With_high_probability '''with high probability'''].
== A Consequence of the Probabilistic Method ==
 
== A Corollary by the Probabilistic Method ==
The analysis of Karger's algorithm implies the following combinatorial proposition for the number of distinct minimum cuts in a graph.
The analysis of Karger's algorithm implies the following combinatorial proposition for the number of distinct minimum cuts in a graph.
{{Theorem|Corollary|
{{Theorem|Corollary|
Line 201: Line 167:
{{Proof|
{{Proof|
Let <math>\mathcal{C}</math> denote the set of all minimum cuts in <math>G</math>. For each min-cut <math>C\in\mathcal{C}</math>, let <math>A_C</math> denote the event "<math>C</math> is returned by ''RandomContract''", whose probability is given by  
Let <math>\mathcal{C}</math> denote the set of all minimum cuts in <math>G</math>. For each min-cut <math>C\in\mathcal{C}</math>, let <math>A_C</math> denote the event "<math>C</math> is returned by ''RandomContract''", whose probability is given by  
:<math>p_C=\Pr[A_C]\,</math>.  
:<math>p_C=\Pr(A_C)\,</math>.  


Clearly we have:
Clearly we have:
Line 209: Line 175:
Due to the [https://en.wikipedia.org/wiki/Probability_axioms#Third_axiom '''additivity of probability'''], it holds that
Due to the [https://en.wikipedia.org/wiki/Probability_axioms#Third_axiom '''additivity of probability'''], it holds that
:<math>
:<math>
p_{\text{correct}}=\sum_{C\in\mathcal{C}}\Pr[A_C]=\sum_{C\in\mathcal{C}}p_C.
p_{\text{correct}}=\sum_{C\in\mathcal{C}}\Pr(A_C)=\sum_{C\in\mathcal{C}}p_C.
</math>
</math>


Line 218: Line 184:


Note that the statement of this theorem has no randomness at all, while the proof consists of a randomized procedure. This is an example of [http://en.wikipedia.org/wiki/Probabilistic_method the probabilistic method].
Note that the statement of this theorem has no randomness at all, while the proof consists of a randomized procedure. This is an example of [http://en.wikipedia.org/wiki/Probabilistic_method the probabilistic method].
== Fast Min-Cut ==
In the analysis of ''RandomContract'' algorithm, recall that we lower bound the probability <math>p_C</math> that a min-cut <math>C</math> is returned by ''RandomContract'' by the following '''telescopic product''':
:<math>p_C\ge\prod_{i=1}^{n-2}\left(1-\frac{2}{n-i+1}\right)</math>.
Here the index <math>i</math> corresponds to the <math>i</math>th contraction. The factor <math>\left(1-\frac{2}{n-i+1}\right)</math> is decreasing in <math>i</math>, which means:
* The probability of success is only getting bad when the graph is getting "too contracted", that is, when the number of remaining vertices is getting small.
This motivates us to consider the following alternation to the algorithm: first using random contractions to reduce the number of vertices to a moderately small number, and then recursively finding a min-cut in this smaller instance. This seems just a restatement of exactly what we have been doing. Inspired by the idea of boosting the accuracy via independent repetition, here we apply the recursion on ''two'' smaller instances generated independently.
The algorithm obtained in this way is called ''FastCut''. We first define a procedure to randomly contract edges until there are <math>t</math> number of vertices left.
{{Theorem|''RandomContract''<math>(G, t)</math>|
:'''Input:''' multi-graph <math>G(V,E)</math>, and integer <math>t\ge 2</math>;
----
:while <math>|V|>t</math> do
:* choose an edge <math>uv\in E</math> uniformly at random;
:* <math>G=Contract(G,uv)</math>;
:return <math>G</math>;
}}
The ''FastCut'' algorithm is recursively defined as follows.
{{Theorem|''FastCut''<math>(G)</math>|
:'''Input:''' multi-graph <math>G(V,E)</math>;
----
:if <math>|V|\le 6</math> then return a mincut by brute force;
:else let <math>t=\left\lceil1+|V|/\sqrt{2}\right\rceil</math>;
:: <math>G_1=RandomContract(G,t)</math>;
:: <math>G_2=RandomContract(G,t)</math>;
::return the smaller one of <math>FastCut(G_1)</math> and <math>FastCut(G_2)</math>;
}}
As before, all <math>G</math> are multigraphs.
Fix a min-cut <math>C</math> in the original multigraph <math>G</math>. By the same analysis as in the case of ''RandomContract'', we have
:<math>
\begin{align}
&\Pr[C\text{ survives all contractions in }RandomContract(G,t)]\\
=
&\prod_{i=1}^{n-t}\Pr[C\text{ survives the }i\text{-th contraction}\mid C\text{ survives the first }(i-1)\text{-th contractions}]\\
\ge
&\prod_{i=1}^{n-t}\left(1-\frac{2}{n-i+1}\right)\\
=
&\prod_{k=t+1}^{n}\frac{k-2}{k}\\
=
&\frac{t(t-1)}{n(n-1)}.
\end{align}
</math>
When <math>t=\left\lceil1+n/\sqrt{2}\right\rceil</math>, this probability is at least <math>1/2</math>. The choice of <math>t</math> is due to our purpose to make this probability at least <math>1/2</math>. You will see this is crucial in the following analysis of accuracy.
We denote by <math>A</math> and <math>B</math> the following events:
:<math>
\begin{align}
A:
&\quad C\text{  survives all contractions in }RandomContract(G,t);\\
B:
&\quad\text{size of min-cut is unchanged after }RandomContract(G,t);
\end{align}
</math>
Clearly, <math>A</math> implies <math>B</math> and by above analysis <math>\Pr[B]\ge\Pr[A]\ge\frac{1}{2}</math>.
We denote by <math>p(n)</math> the lower bound on the probability that <math>FastCut(G)</math> succeeds for a multigraph of <math>n</math> vertices, that is
:<math>
p(n)
=\min_{G: |V|=n}\Pr[\,FastCut(G)\text{ returns a min-cut in }G\,].
</math>
Suppose that <math>G</math> is the multigraph that achieves the minimum in above definition. The following recurrence holds for <math>p(n)</math>.
:<math>
\begin{align}
p(n)
&=
\Pr[\,FastCut(G)\text{ returns a min-cut in }G\,]\\
&=
\Pr[\,\text{ a min-cut of }G\text{ is returned by }FastCut(G_1)\text{ or }FastCut(G_2)\,]\\
&\ge
1-\left(1-\Pr[B\wedge FastCut(G_1)\text{ returns a min-cut in }G_1\,]\right)^2\\
&\ge
1-\left(1-\Pr[A\wedge FastCut(G_1)\text{ returns a min-cut in }G_1\,]\right)^2\\
&=
1-\left(1-\Pr[A]\Pr[ FastCut(G_1)\text{ returns a min-cut in }G_1\mid A]\right)^2\\
&\ge
1-\left(1-\frac{1}{2}p\left(\left\lceil1+n/\sqrt{2}\right\rceil\right)\right)^2,
\end{align}
</math>
where <math>A</math> and <math>B</math> are defined as above such that <math>\Pr[A]\ge\frac{1}{2}</math>.
The base case is that  <math>p(n)=1</math> for <math>n\le 6</math>. By induction it is easy to prove that
:<math>
p(n)=\Omega\left(\frac{1}{\log n}\right).
</math>
Recall that we can implement an edge contraction in <math>O(n)</math> time, thus it is easy to verify the following recursion of time complexity:
:<math>
T(n)=2T\left(\left\lceil1+n/\sqrt{2}\right\rceil\right)+O(n^2),
</math>
where <math>T(n)</math> denotes the running time of <math>FastCut(G)</math> on a multigraph <math>G</math> of <math>n</math> vertices.
By induction with the base case <math>T(n)=O(1)</math> for <math>n\le 6</math>, it is easy to verify that <math>T(n)=O(n^2\log n)</math>.
{{Theorem
|Theorem|
: For any multigraph with <math>n</math> vertices, the ''FastCut'' algorithm returns a minimum cut with probability <math>\Omega\left(\frac{1}{\log n}\right)</math> in time <math>O(n^2\log n)</math>.
}}
At this point, we see the name ''FastCut'' is misleading because it is actually slower than the original ''RandomContract'' algorithm, only the chance of successfully finding a min-cut is much better (improved from an <math>\Omega(1/n^2)</math> to an <math>\Omega(1/\log n)</math>).
Given any input multi-graph, repeatedly running the ''FastCut'' algorithm independently for some <math>O((\log n)^2)</math> times and returns the smallest cut ever returned, we have an algorithm which runs in time <math>O(n^2\log^3n)</math> and returns a min-cut with probability <math>1-O(1/n)</math>, i.e. with high probability.
Recall that the running time of best known deterministic algorithm for min-cut on multi-graph is <math>O(mn+n^2\log n)</math>. On dense graph, the randomized algorithm outperforms the best known deterministic algorithm.
Finally, Karger further improves this and obtains a near-linear (in the number of edges) time [https://arxiv.org/abs/cs/9812007 randomized algorithm] for minimum cut in multi-graphs.

Latest revision as of 02:36, 12 March 2023

Let [math]\displaystyle{ G(V, E) }[/math] be an undirected graph. A subset [math]\displaystyle{ C\subseteq E }[/math] of edges is a cut of graph [math]\displaystyle{ G }[/math] if [math]\displaystyle{ G }[/math] becomes disconnected after deleting all edges in [math]\displaystyle{ C }[/math].

Let [math]\displaystyle{ \{S,T\} }[/math] be a bipartition of [math]\displaystyle{ V }[/math] into nonempty subsets [math]\displaystyle{ S,T\subseteq V }[/math], where [math]\displaystyle{ S\cap T=\emptyset }[/math] and [math]\displaystyle{ S\cup T=V }[/math]. A cut [math]\displaystyle{ C }[/math] is specified by this bipartition as

[math]\displaystyle{ C=E(S,T)\, }[/math],

where [math]\displaystyle{ E(S,T) }[/math] denotes the set of "crossing edges" with one endpoint in each of [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math], formally defined as

[math]\displaystyle{ E(S,T)=\{uv\in E\mid u\in S, v\in T\} }[/math].

The min-cut problem, also called the global minimum cut problem, is defined as follows.

Min-cut problem
  • Input: an undirected graph [math]\displaystyle{ G(V,E) }[/math];
  • Output: a cut [math]\displaystyle{ C }[/math] in [math]\displaystyle{ G }[/math] with the smallest size [math]\displaystyle{ |C| }[/math].

Equivalently, the problem asks to find a bipartition of [math]\displaystyle{ V }[/math] into disjoint non-empty subsets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] that minimizes [math]\displaystyle{ |E(S,T)| }[/math].

We consider the problem in a slightly more generalized setting, where the input graphs [math]\displaystyle{ G }[/math] can be multi-graphs, meaning that there could be multiple parallel edges between two vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]. The cuts in multi-graphs are defined in the same way as before, and the cost of a cut [math]\displaystyle{ C }[/math] is given by the total number of edges (including parallel edges) in [math]\displaystyle{ C }[/math]. Equivalently, one may think of a multi-graph as a graph with integer edge weights, and the cost of a cut [math]\displaystyle{ C }[/math] is the total weights of all edges in [math]\displaystyle{ C }[/math].

A canonical deterministic algorithm for this problem is through the max-flow min-cut theorem. The max-flow algorithm finds us a minimum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, which disconnects a source [math]\displaystyle{ s\in V }[/math] from a sink [math]\displaystyle{ t\in V }[/math], both specified as part of the input. A global min cut can be found by exhaustively finding the minimum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut for an arbitrarily fixed source [math]\displaystyle{ s }[/math] and all possible sink [math]\displaystyle{ t\neq s }[/math].

Karger's Algorithm

We will describe a simple and elegant randomized algorithm for the min-cut problem. The algorithm is due to David Karger.

Let [math]\displaystyle{ G(V, E) }[/math] be a multi-graph, which allows more than one parallel edges between two distinct vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] but does not allow any self-loops: the edges that adjoin a vertex to itself. A multi-graph [math]\displaystyle{ G }[/math] can be represented by an adjacency matrix [math]\displaystyle{ A }[/math], in the way that each non-diagonal entry [math]\displaystyle{ A(u,v) }[/math] takes nonnegative integer values instead of just 0 or 1, representing the number of parallel edges between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] in [math]\displaystyle{ G }[/math], and all diagonal entries [math]\displaystyle{ A(v,v)=0 }[/math] (since there is no self-loop).

Given a multi-graph [math]\displaystyle{ G(V,E) }[/math] and an edge [math]\displaystyle{ e\in E }[/math], we define the following contraction operator Contract([math]\displaystyle{ G }[/math], [math]\displaystyle{ e }[/math]), which transform [math]\displaystyle{ G }[/math] to a new multi-graph.

The contraction operator Contract([math]\displaystyle{ G }[/math], [math]\displaystyle{ e }[/math])
say [math]\displaystyle{ e=uv }[/math]:
  • replace [math]\displaystyle{ \{u,v\} }[/math] by a new vertex [math]\displaystyle{ x }[/math];
  • for every edge (no matter parallel or not) in the form of [math]\displaystyle{ uw }[/math] or [math]\displaystyle{ vw }[/math] that connects one of [math]\displaystyle{ \{u,v\} }[/math] to a vertex [math]\displaystyle{ w\in V\setminus\{u,v\} }[/math] in the graph other than [math]\displaystyle{ u,v }[/math], replace it by a new edge [math]\displaystyle{ xw }[/math];
  • the reset of the graph does not change.

In other words, the [math]\displaystyle{ Contract(G,uv) }[/math] merges the two vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] into a new vertex [math]\displaystyle{ x }[/math] whose incident edges preserves the edges incident to [math]\displaystyle{ u }[/math] or [math]\displaystyle{ v }[/math] in the original graph [math]\displaystyle{ G }[/math] except for the parallel edges between them. Now you should realize why we consider multi-graphs instead of simple graphs, because even if we start with a simple graph without parallel edges, the contraction operator may create parallel edges.

The contraction operator is illustrated by the following picture:

Karger's algorithm uses a simple idea:

  • At each step we randomly select an edge in the current multi-graph to contract until there are only two vertices left.
  • The parallel edges between these two remaining vertices must be a cut of the original graph.
  • We return this cut and hope that with good chance this gives us a minimum cut.

The following is the pseudocode for Karger's algorithm.

RandomContract (Karger 1993)
Input: multi-graph [math]\displaystyle{ G(V,E) }[/math];
while [math]\displaystyle{ |V|\gt 2 }[/math] do
  • choose an edge [math]\displaystyle{ uv\in E }[/math] uniformly at random;
  • [math]\displaystyle{ G=Contract(G,uv) }[/math];
return [math]\displaystyle{ C=E }[/math] (the parallel edges between the only two vertices in [math]\displaystyle{ V }[/math]);

Another way of looking at the contraction operator Contract([math]\displaystyle{ G }[/math],[math]\displaystyle{ e }[/math]) is that it unions two classes of vertices. Let [math]\displaystyle{ V=\{v_1,v_2,\ldots,v_n\} }[/math] be the set of all vertices. We start with [math]\displaystyle{ n }[/math] vertex classes [math]\displaystyle{ S_1,S_2,\ldots, S_n }[/math] with each class [math]\displaystyle{ S_i=\{v_i\} }[/math] contains one vertex. By calling [math]\displaystyle{ Contract(G,uv) }[/math], where [math]\displaystyle{ u\in S_i }[/math] and [math]\displaystyle{ v\in S_j }[/math] for distinct [math]\displaystyle{ i\neq j }[/math], we take union of [math]\displaystyle{ S_i }[/math] and [math]\displaystyle{ S_j }[/math]. The edges in the contracted multi-graph are the edges that cross between different vertex classes.

This view of contraction is illustrated by the following picture:

Analysis of Karger's Algorithm

We now analyze the above algorithm. Since the algorithm is randomized, its output cut is random even when the input is fixed, so the output may not always be correct. We want to give a theoretical guarantee of the chance that the algorithm returns a correct answer on an arbitrary input.

More precisely, on an arbitrarily fixed input multi-graph [math]\displaystyle{ G }[/math], we want to answer the following question rigorously:

[math]\displaystyle{ p_{\text{correct}}=\Pr[\,\text{a minimum cut is returned by }RandomContract\,]\ge ? }[/math]

To answer this question, we prove a stronger statement: for arbitrarily fixed input multi-graph [math]\displaystyle{ G }[/math] and a particular minimum cut [math]\displaystyle{ C }[/math] in [math]\displaystyle{ G }[/math],

[math]\displaystyle{ p_{C}=\Pr[\,C\mbox{ is returned by }RandomContract\,]\ge ? }[/math]

Obviously this will imply the previous lower bound for [math]\displaystyle{ p_{\text{correct}} }[/math] because the event in [math]\displaystyle{ p_{C} }[/math] implies the event in [math]\displaystyle{ p_{\text{correct}} }[/math].

  • In above argument we use the simple law in probability that [math]\displaystyle{ \Pr(A)\le \Pr(B) }[/math] if [math]\displaystyle{ A\subseteq B }[/math], i.e. event [math]\displaystyle{ A }[/math] implies event [math]\displaystyle{ B }[/math].

We introduce the following notations:

  • Let [math]\displaystyle{ e_1,e_2,\ldots,e_{n-2} }[/math] denote the sequence of random edges chosen to contract in a running of RandomContract algorithm.
  • Let [math]\displaystyle{ G_1=G }[/math] denote the original input multi-graph. And for [math]\displaystyle{ i=1,2,\ldots,n-2 }[/math], let [math]\displaystyle{ G_{i+1}=Contract(G_{i},e_i) }[/math] be the multigraph after [math]\displaystyle{ i }[/math]th contraction.

Obviously [math]\displaystyle{ e_1,e_2,\ldots,e_{n-2} }[/math] are random, and they are the only random choices used in the algorithm: meaning that they along with the input [math]\displaystyle{ G }[/math], uniquely determine the sequence of multi-graphs [math]\displaystyle{ G_1,G_2,\ldots,G_{n-2} }[/math] in every iteration as well as the final output.

We now compute the probability [math]\displaystyle{ p_C }[/math] by decompose it into more elementary events involving [math]\displaystyle{ e_1,e_2,\ldots,e_{n-2} }[/math]. This is due to the following proposition.

Proposition 1
If [math]\displaystyle{ C }[/math] is a minimum cut in a multi-graph [math]\displaystyle{ G }[/math] and [math]\displaystyle{ e\not\in C }[/math], then [math]\displaystyle{ C }[/math] is still a minimum cut in the contracted graph [math]\displaystyle{ G'=contract(G,e) }[/math].
Proof.

We first observe that contraction will never create new cuts: every cut in the contracted graph [math]\displaystyle{ G' }[/math] must also be a cut in the original graph [math]\displaystyle{ G }[/math].

We then observe that a cut [math]\displaystyle{ C }[/math] in [math]\displaystyle{ G }[/math] "survives" in the contracted graph [math]\displaystyle{ G' }[/math] if and only if the contracted edge [math]\displaystyle{ e\not\in C }[/math].

Both observations are easy to verify by the definition of contraction operator (in particular, easier to verify if we take the vertex class interpretation).

[math]\displaystyle{ \square }[/math]

Recall that [math]\displaystyle{ e_1,e_2,\ldots,e_{n-2} }[/math] denote the sequence of random edges chosen to contract in a running of RandomContract algorithm.

By Proposition 1, the event [math]\displaystyle{ \mbox{``}C\mbox{ is returned by }RandomContract\mbox{''}\, }[/math] is equivalent to the event [math]\displaystyle{ \mbox{``}e_i\not\in C\mbox{ for all }i=1,2,\ldots,n-2\mbox{''} }[/math]. Therefore:

[math]\displaystyle{ \begin{align} p_C &= \Pr[\,C\mbox{ is returned by }{RandomContract}\,]\\ &= \Pr[\,e_i\not\in C\mbox{ for all }i=1,2,\ldots,n-2\,]\\ &= \prod_{i=1}^{n-2}\Pr[e_i\not\in C\mid \forall j\lt i, e_j\not\in C]. \end{align} }[/math]

The last equation is due to the chain rule.

Now our task is to give lower bound to each [math]\displaystyle{ p_i=\Pr[e_i\not\in C\mid \forall j\lt i, e_j\not\in C] }[/math]. The condition [math]\displaystyle{ \mbox{``}\forall j\lt i, e_j\not\in C\mbox{''} }[/math] means the min-cut [math]\displaystyle{ C }[/math] survives all first [math]\displaystyle{ i-1 }[/math] contractions [math]\displaystyle{ e_1,e_2,\ldots,e_{i-1} }[/math], which due to Proposition 1 means that [math]\displaystyle{ C }[/math] is also a min-cut in the multi-graph [math]\displaystyle{ G_i }[/math] obtained from applying the first [math]\displaystyle{ (i-1) }[/math] contractions.

Then the conditional probability [math]\displaystyle{ p_i=\Pr[e_i\not\in C\mid \forall j\lt i, e_j\not\in C] }[/math] is the probability that no edge in [math]\displaystyle{ C }[/math] is hit when a uniform random edge in the current multi-graph is chosen assuming that [math]\displaystyle{ C }[/math] is a minimum cut in the current multi-graph. Intuitively this probability should be bounded from below, because as a min-cut [math]\displaystyle{ C }[/math] should be sparse among all edges. This intuition is justified by the following proposition.

Proposition 2
If [math]\displaystyle{ C }[/math] is a min-cut in a multi-graph [math]\displaystyle{ G(V,E) }[/math], then [math]\displaystyle{ |E|\ge \frac{|V||C|}{2} }[/math].
Proof.
It must hold that the degree of each vertex [math]\displaystyle{ v\in V }[/math] is at least [math]\displaystyle{ |C| }[/math], or otherwise the set of edges incident to [math]\displaystyle{ v }[/math] forms a cut of size smaller than [math]\displaystyle{ |C| }[/math] which separates [math]\displaystyle{ \{v\} }[/math] from the rest of the graph, contradicting that [math]\displaystyle{ C }[/math] is a min-cut. And the bound [math]\displaystyle{ |E|\ge \frac{|V||C|}{2} }[/math] follows directly from applying the handshaking lemma to the fact that every vertex in [math]\displaystyle{ G }[/math] has degree at least [math]\displaystyle{ |C| }[/math].
[math]\displaystyle{ \square }[/math]

Let [math]\displaystyle{ V_i }[/math] and [math]\displaystyle{ E_i }[/math] denote the vertex set and edge set of the multi-graph [math]\displaystyle{ G_i }[/math] respectively, and recall that [math]\displaystyle{ G_i }[/math] is the multi-graph obtained from applying first [math]\displaystyle{ (i-1) }[/math] contractions. Obviously [math]\displaystyle{ |V_{i}|=n-i+1 }[/math]. And due to Proposition 2, [math]\displaystyle{ |E_i|\ge \frac{|V_i||C|}{2} }[/math] if [math]\displaystyle{ C }[/math] is still a min-cut in [math]\displaystyle{ G_i }[/math].

The probability [math]\displaystyle{ p_i=\Pr[e_i\not\in C\mid \forall j\lt i, e_j\not\in C] }[/math] can be computed as

[math]\displaystyle{ \begin{align} p_i &=1-\frac{|C|}{|E_i|}\\ &\ge1-\frac{2}{|V_i|}\\ &=1-\frac{2}{n-i+1} \end{align}, }[/math]

where the inequality is due to Proposition 2.

We now can put everything together. We arbitrarily fix the input multi-graph [math]\displaystyle{ G }[/math] and any particular minimum cut [math]\displaystyle{ C }[/math] in [math]\displaystyle{ G }[/math].

[math]\displaystyle{ \begin{align} p_{\text{correct}} &=\Pr[\,\text{a minimum cut is returned by }RandomContract\,]\\ &\ge \Pr[\,C\mbox{ is returned by }{RandomContract}\,]\\ &= \Pr[\,e_i\not\in C\mbox{ for all }i=1,2,\ldots,n-2\,]\\ &= \prod_{i=1}^{n-2}\Pr[e_i\not\in C\mid \forall j\lt i, e_j\not\in C]\\ &\ge \prod_{i=1}^{n-2}\left(1-\frac{2}{n-i+1}\right)\\ &= \prod_{k=3}^{n}\frac{k-2}{k}\\ &= \frac{2}{n(n-1)}. \end{align} }[/math]

This gives us the following theorem.

Theorem
For any multigraph with [math]\displaystyle{ n }[/math] vertices, the RandomContract algorithm returns a minimum cut with probability at least [math]\displaystyle{ \frac{2}{n(n-1)} }[/math].

At first glance this seems to be a quite slim chance of success. However, notice that there may be exponential many cuts in a graph (because potentially every nonempty subset [math]\displaystyle{ S\subset V }[/math] corresponds to a cut [math]\displaystyle{ C=E(S,\overline{S}) }[/math]), and Karger's algorithm effectively reduce this exponential-sized space to quadratic-sized, an exponential improvement!

We can run RandomContract independently for [math]\displaystyle{ t=\left\lceil\frac{n(n-1)\ln n}{2}\right\rceil }[/math] times and return the smallest cut ever returned. The probability that a minimum cut is found is at least:

[math]\displaystyle{ \begin{align} &\quad 1-\Pr[\,\mbox{all }t\mbox{ independent runnings of } RandomContract\mbox{ fails to find a min-cut}\,] \\ &= 1-\Pr[\,\mbox{a single running of }{RandomContract}\mbox{ fails}\,]^{t} \\ &\ge 1- \left(1-\frac{2}{n(n-1)}\right)^{\frac{n(n-1)\ln n}{2}} \\ &\ge 1-\frac{1}{n}. \end{align} }[/math]

A Consequence of the Probabilistic Method

The analysis of Karger's algorithm implies the following combinatorial proposition for the number of distinct minimum cuts in a graph.

Corollary
For any graph [math]\displaystyle{ G(V,E) }[/math] of [math]\displaystyle{ n }[/math] vertices, the number of distinct minimum cuts in [math]\displaystyle{ G }[/math] is at most [math]\displaystyle{ \frac{n(n-1)}{2} }[/math].
Proof.

Let [math]\displaystyle{ \mathcal{C} }[/math] denote the set of all minimum cuts in [math]\displaystyle{ G }[/math]. For each min-cut [math]\displaystyle{ C\in\mathcal{C} }[/math], let [math]\displaystyle{ A_C }[/math] denote the event "[math]\displaystyle{ C }[/math] is returned by RandomContract", whose probability is given by

[math]\displaystyle{ p_C=\Pr(A_C)\, }[/math].

Clearly we have:

  • for any distinct [math]\displaystyle{ C,D\in\mathcal{C} }[/math], [math]\displaystyle{ A_C\, }[/math] and [math]\displaystyle{ A_{D}\, }[/math] are disjoint events; and
  • the union [math]\displaystyle{ \bigcup_{C\in\mathcal{C}}A_C }[/math] is precisely the event "a minimum cut is returned by RandomContract", whose probability is given by
[math]\displaystyle{ p_{\text{correct}}=\Pr[\,\text{a minimum cut is returned by } RandomContract\,] }[/math].

Due to the additivity of probability, it holds that

[math]\displaystyle{ p_{\text{correct}}=\sum_{C\in\mathcal{C}}\Pr(A_C)=\sum_{C\in\mathcal{C}}p_C. }[/math]

By the analysis of Karger's algorithm, we know [math]\displaystyle{ p_C\ge\frac{2}{n(n-1)} }[/math]. And since [math]\displaystyle{ p_{\text{correct}} }[/math] is a well defined probability, due to the unitarity of probability, it must hold that [math]\displaystyle{ p_{\text{correct}}\le 1 }[/math]. Therefore,

[math]\displaystyle{ 1\ge p_{\text{correct}}=\sum_{C\in\mathcal{C}}p_C\ge|\mathcal{C}|\frac{2}{n(n-1)} }[/math],

which means [math]\displaystyle{ |\mathcal{C}|\le\frac{n(n-1)}{2} }[/math].

[math]\displaystyle{ \square }[/math]

Note that the statement of this theorem has no randomness at all, while the proof consists of a randomized procedure. This is an example of the probabilistic method.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=概率论与数理统计_(Spring_2023)/Karger%27s_min-cut_algorithm&oldid=10655"