Bases: Graph Cut/ Multi-graphs/ Contraction/ ChainRule/ Induction/

Min-Cut

Min-cut problem:

Input: an undirected graph $G(V,E)$;
Output: a cut $C$ in $G$ with the smallest size $|C|$.

A canonical deterministic algorithm for this problem is through the max-flow min-cut theorem. Actually, max-flow is a dual problem of min-cut, when max-flow solved, min-cut solved. This takes $(n-1)\times maxFlowTime$ where $n=|V|$ is the number of vertices.

With contraction, 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.

RandomContract(Karger 1993)
$\quad$Input: multi-graph $G(V,E)$.
$\quad$while $|V|>2$ do

choose an edge $uv\in E$ uniformly at random;
$G=Contract(G,uv)$;

$\quad$return $C=E(v_{n-1},v_n)$.

With suitable choice of data structures, each operation $Contract(G,e)$ can be implemented within running time $O(n)$ where $n = | V |$ is the number of vertices. (By using the bucket sort.)
Thus, RandomContract can be done in $O(n^2)$ with $n$ vertices.

Analysis of accuracy(RandomContract):

Proposition 1:
$\quad$If $C$ is a minimum cut in a multi-graph $G$ and $e\notin C$, then $C$ is still a minimum cut in the contracted graph $G^{‘}=Contract(G,e)$.
Proposition 2:
$\quad$If $C$ is a min-cut in a multi-graph $G(V,E)$, then $|E|\geq\frac{|V||C|}{2}$.

We arbitrarily fix the input multi-graph $G$ and any particular minimum cut $C$ in $G$.

\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}
This gives us the following theorem:
For any multigraph with n vertices, the RandomContract algorithm returns a minimum cut with probability at least $\frac{2}{n(n-1)}$.
And by $t=\frac{n(n-1)ln\ n}{2}$ times independently running, i.e. $O(n^4log\ n)$, we can found a minimum cut with high probability($1-\frac1n$).

A Corollary:
For any graph G(V,E) of n vertices, the number of distinct minimum cuts in G is at most $\frac{n(n-1)}{2}$.

Fast Min-Cut

Recall calculating lower bound of $p$, the factor $(1-\frac2{n-i+1})$ is decreasing as $i$ increases. Idea is to stopping when $G$ becomes small enough.

RandomContract$(G, t)$
$\quad$Input: multi-graph $G(V,E)$, and integer $t\geq2$.
$\quad$while $|V|>t$ do

choose an edge $uv\in E$ uniformly at random;
$G=Contract(G,uv)$;

$\quad$return G.

The FastCut algorithm is recursively defined as follows.
FastCut(G)
$\quad$Input: multi-graph G(V,E);
$\quad$if $|V|\neq6$ then return a mincut by brute force;
$\quad$else let $t=\left \lceil 1+|V|/\sqrt2 \right \rceil$:
$\qquad G_1=RandomContract(G,t);$
$\qquad G_2=RandomContract(G,t);$
$\qquad$return the smaller one of $FastCut(G_1)$ and $FastCut(G_2)$.

By the same analysis as in the case of RandomContract, we have

\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}

when $t=\left \lceil 1+|V|/\sqrt2 \right \rceil$, this probability is at least 1/2 due to fixed $t$.

analysis of accuracy

Let $A$ be C survives all contractions in RandomContract(G,t);
Let $B$ be size of min-cut is unchanged after RandomContract(G,t);

\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}
The base case is that $p(n)=1$ for $n\neq6$, and $p(n)=\omega(\frac1{log\ n})$.

Similarly, time complexity: $T(n)=2T(\left \lceil 1+n/\sqrt2 \right \rceil)+O(n^2)$. With the base case $T(n)=O(1)$ for $n\neq6$, $T(n)=O(n^2log\ n)$.

Max-Cut

Max-cut problem:

Input: an undirected graph $G(V,E)$;
Output: a cut $C$ in $G$ with the largest size $|C|$.

a typical MAX-CSP problem ???

Since the problem is NP-hard, we may compromise our goal and allow algorithm to not always find the optimal solution. However, we still want to guarantee that the algorithm always returns a relatively good solution on all possible instances. This notion is formally captured by approximation algorithms and approximation ratio.

Approximation ratio
Considering a greedy algorithm that trying to maximize the current $|E(S,T)|$ at every step. Let $SOL_G$ be the size of the cut $|E(S,T)|$ returned by the greedy algorithm. It is trivial that $SOL_G\neq OPT_G$. We say the approximation ratio of the greedy algorithm is $\alpha$ for some $0<\alpha\neq1$, if $\frac{SOL_G}{OPT_G}\geq \alpha$ for every possible instance $G$ of max-cut.
The GreedyMaxCut is a 0.5-approximation algorithm for the max-cut problem.

\begin{align}
SOL_G
&= \sum_{i=1}^n\max\left(|E(S_i, \{v_i\})|,|E(T_i, \{v_i\})|\right)\\
&\ge \frac{1}{2}\sum_{i=1}^n\left(|E(S_i, \{v_i\})|+|E(T_i, \{v_i\})|\right)\\
&=\frac{1}{2}|E|\\
&\ge\frac{1}{2}OPT_G.
\end{align}

Derandomization by conditional expectation

The greedy algorithm for max-cut is actually due to a derandomization of average-case。

Derandomization by pairwise independence

Enumerate vertices as $V=\{v_1,v_2,\ldots,v_n\}$.
let $k=\lceil\log (n+1)\rceil$;
for all $\vec{x}\in\{0,1\}^k$:
$\qquad$initialize $S_{\vec{x}}=T_{\vec{x}}=\emptyset$;
$\qquad$for $i=1, 2, \ldots, n$
$\qquad\quad$if $\bigoplus_{j:\lfloor i/2^j\rfloor\bmod 2=1}x_j=1$
$\qquad\quad$else $v_i$ joins $T_{\vec{x}}$;
return the $\{S_{\vec{x}},T_{\vec{x}}\}$ with the largest $|E(S_{\vec{x}},T_{\vec{x}})|$.

The algorithm has approximation ratio 1/2 and runs in polynomial time.