User:Daiyuda/sandbox

The General Min-cut Problem

Description

The example of Min-Cut Problem

This problem is that given an undirected graph G(V, E), try to find a partition that divides the G into two non-empty node sets S and T (S+T=V) that minimizes the number of crossed edges between S and T.
Input: a undirected graphG(V, E);
Output: The number of crossed edges between S and T for a partition that divides the G into two non-empty node sets S and T (S+T=V)
Goal:

$minimize\sum _{(u,v)\in S\times T}{c(u,v)}$.

Example

As you can tell from the picture in the right, the line in red is a cut,and the number of crossed edges is 3, however it is not a min cut. While the line in green is the min-cut of this graph, and the number of crossed edges is 2.

The Karger's Basic Algorithm

Algorithm Description

In computer science and graph theory, Karger's algorithm is a Monte Carlo method to compute the minimum cut of a connected graph. It is developed by David Karger.
Before describing the algorithm, we have to define the contraction of two nodes, which is to combine two different nodes u and v, in a graph, as a new node u' with edges that were connected with either u or v, except for the edge(s) connecting u and v.
An example of contraction is displayed:
This algorithm is shown as below:

   INPUT:  An undirected graph G = (V, E)

   OUTPUT: The the min-cut of G
   function Kager's Min-Cut(G):
      1, Let T equals θ(n^2) = cn*(n-1)/2;
      2, while (T-- >= 0) 
      3,     while (there are more than 2 nodes left in the graph)
      4,         randomly pick an edge in G, (u, v) ∈ E;
      5,         replace u and v with the contraction of those two nodes, u';
      6,     Keep record of the number of edges between those two super nodes, if the new result is smaller than the previous one, replace the previous result with the new one;
      7, return the result that is the smallest number of edges between two super nodes.
   end function

This is an example of executing the inner while loop of Karger's Basic algorithm once. There are 5 nodes and 7 edges in the graph G. The min-cut of G is 2, while after one execution of the inner while loop, the cut is 4.

Proof of Correctness

Lemma 1: let k denote the actual result of the min-cut of G, every node in the graph has a degree that is equal or larger than k.

Proof: If there exists a node N in G, whose degree is smaller than k, then select N as on one side and the other nodes on the other side. As a result we get a min-cut which is smaller than k. This is a contradiction. ∎

Theorem: With high probability we can find the min-cut of given graph G by executing Karger's Min-Cut Algorithm. 

Proof: Let C denote the edge set of minimum k-cut. At each stage. we have n-i node and by Lemma 1 there are at least (n-i)*k⁄2 edges. As such, the probability of selecting an edge in C to make a contraction is

$Pr[(u,v)\in C]\leq {\frac {k}{(n-i)*k/2}}={\frac {2}{n-i}}$

In this manner, we have to run (n-2) iterations to reduce a graph of n nodes to a graph of only two nodes with i from 0 to n-3. Thus, the probability of C surviving after (n-2) iterations is

${\begin{aligned}Pr[C]&\geq \prod _{i=0}^{n-3}{(1-{\frac {2}{n-i}})}\\&=(1-{\frac {2}{n}})(1-{\frac {2}{n-1}})(1-{\frac {2}{n-2}})\cdots ({\frac {1}{3}})\\&={\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}}\\&={\frac {2}{n(n-1)}}\end{aligned}}$

Therefore, we have at least Ω(1/n²) chances to find the min-cut C for executing the inner while loop of Karger's Basic Algorithm once. Suppose Pr[Failure] indicates that the probability of failing finding the min-cut via executing the inner while loop once. As such if we execute the inner while loop T = c*n*(n-1)/2 = O(n²) times, the probability of successfully returning C is

${\begin{aligned}Pr[FinalSuccess]&\geq 1-Pr[Failure]^{T}\\&=1-(1-{\frac {2}{n(n-1)}})^{T}\\&=1-(1-{\frac {2}{n(n-1)}})^{\frac {cn(n-1)}{2}}\\&=1-{\frac {1}{e^{c}}}>99\%~when~c~=~10.\end{aligned}}$

Running Time

Lemma 2: For each execution of the inner while loop (Line 3- 5) of Karger's Basic Algorithm, it takes $O(n^{2})$  running time.

Proof: We can represent this graph G by maintaining an adjacency list, which means all edges incident to node v are in a linked list. What is more, we have to construct pointers between the two copies the the same edge (u, w) and (w, u). When v and w are contracted, we traverse the adjacency list of v, and for each edge (v, u) find the corresponding edge(u, v) by the pointer and rename it to (u, w). As such, each contraction costs O(n) time and we have to contract (n-2) times, which in total is O(n²).∎

According to the algorithm, we have to repeat the inner while loop of Karger's Basic Algorithm O(n²) times. Hence, with the correctness of lemma 2, the overall running time is O(n⁴).

The Karger-Stein's Algorithm

This algorithm is developed by David Karger and Clifford Stein. And it is an order of magnitude improvement of the running time compared with Karger's Basic Algorithm . .
Before we move forwards to the detailed description, we notice that when we do the contractions until i vertices are left, the probability that C survives is

${\begin{aligned}Pr[C]&\geq \prod _{j=0}^{n-i}{(1-{\frac {2}{n-j}})}\\&={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1}}\cdot {\frac {n-4}{n-2}}\cdots {\frac {n-i}{n-i+2}}\cdot {\frac {n-i-1}{n-i+1}}\cdot {\frac {n-i-2}{n-i}}\\&={\frac {(n-i-1)(n-i-2)}{n(n-1)}}\\&\in O({\frac {i^{2}}{n^{2}}})\end{aligned}}$

Algorithm Description

Inspired by the formula above, we can find that the less edges that left in this graph, the less chance that C survives. We, therefore, improve the basic algorithm that

   INPUT:  An undirected graph G = (V, E)

   OUTPUT: find the the min-cut of G
   function Kager-Stein's Min-Cut(G):
      1, run the Karger's Basic Algorithm to i = n⁄√2  twice getting G1 and G2,
      2, recursively run the Karger-Stein's Min-Cut Algorithm on G1 and G2
   end function

Running Time

Then we can get the probability of min cut survive P(n) (n is the number of vertices) meets this recurrence relation:

$P(n)=1-(1-{\frac {1}{2}}P({\frac {n}{\sqrt {2}}}))^{2}$

Also, we can prove that $P(n)=O({\frac {1}{\ln n}})$. and the recurrence relation of running time is

$T(n)=2T({\frac {n}{\sqrt {2}}})+O(n^{2})$ and $T(n)=O(1)$ when n ≤ 2.

According to the Master Theorem, $T(n)=O(n^{2}\ln n)$. Therefore the overall running time is $T(n)\cdot {\frac {1}{P(n)}}=O(n^{2}\ln ^{2}n)$, which is an order of magnitude improvement.

Finding All Min-Cuts

Thereom: With high probability we can find all min cuts in the running time of $O(n^{2}\ln ^{3}n)$.

Proof: Since we know that $P(n)=O({\frac {1}{\ln n}})$, therefore after running this algorithm $O(\ln ^{2}n)$ times The probability of missing a specific min-cut is

$Pr[miss~a~specific~min-cut]=(1-P(n))^{O(\ln ^{2}n)}\leq (1-{\frac {c}{\ln n}})^{\frac {3\ln ^{2}n}{c}}\leq e^{-3\ln n}={\frac {1}{n^{3}}}$.

And there are at most ${\binom {n}{2}}$ min-cuts, hence the probability of missing ant min-cut is

$Pr[miss~any~min-cut]\leq {\binom {n}{2}}\cdot {\frac {1}{n^{3}}}=O({\frac {1}{n}}).$

Known to all, the probability of failures is considerably small when n is large enough.∎

Improvement Bound

To determine a min-cut, one has to touch every edges in the graph at least once, which is $O(n^{2})$ time. And the Karger-Stein's Min-Cut Algorithm which is so far the fastest , takes the running time of $O(n^{2}\ln ^{O(1)}n)$, which is really close.

References

Category:Graph algorithms Category:Graph connectivity