Minimum Cut

deterministic algorithms

• Max-flow
• Gabow

Recursive Contraction Algorithm

Recall contraction algorithm

• success probability $1/n^2$
• why?
• high failure probability when graph is small
• how fix? repetition
• how do better? repeat only on small problems!

Idea

• Contract to $s$ vertices, then run a cubic algorithm
• Single trial runtime $m+s^3$ or let's say $n^2+s^3$
• Success probability $(s/n)^2$
• So need to repeat $(n/s)^2$ times
• Overall runtime $n^4/s^2 + n^2s = n^2(n^2/s^2+s)$
• Balance at $n^2=s^3$ i.e. $s=n^{2/3}$
• Runtime $n^{8/3}$, an improvement!
• Redo analysis with faster algorithm.
  • Single trial runtime $n^2 + s^{8/3}$
  • need $(n/s)^2$ trials
  • Runtime $(n/s)^2(n^2 + s^{8/3}) = n^4/s^2 + n^2s^{2/3} = n^2(n^2/s^2 + s^{2/3})$
  • balance at $n^2=s^{8/3}$ ie $s=n^{3/4}$
  • runtime $n^{5/2}$, more improvement

$$ \begin{align*} T(n) &=2T(n/\sqrt{2})+O(n^2) = O(n^2\log n)\\ P(n) &=1-(1-\frac12P(n/\sqrt{2}))^2\\ p_k &=1-(1-\frac12p_{k-1})^2\\ &=p_{k-1}-\frac14p_{k-1}^2 \end{align*} $$ Back-envelope:

• subtracting $p_{k-1}/4$ fraction of $p_{k-1}$ each time
• so requires about $4/p_{k-1}$ levels to cut $p_{k-1}$ in half.
• if $q_k=1/p_k$, requires about $q_k$ steps to double $q_k$
• i.e. $q_{2k}=2q_k$
• so $q_k=k$
• and $p_k=1/k$

Formalize: $$ \begin{align*} z_k&=4/p_k-1\\ p_k&=4/(z_k+1)\\ z_{k+1}&=z_k+1+1/z_k\\ k < z_k &< k+H_{k-1}+3 \end{align*} $$

Sampling

Min-cut

• saw RCA, $\Olog(n^2)$ time
• Another candidate: Gabow's algorithm: $\Olog(mc)$ time on $m$-edge graph with min-cut $c$
• nice algorithm, if $m$ and $c$ small. But how could we make that happen?
• Similarly, for those who know about it, augmenting paths gives $O(mv)$ for max flow. Good if $m$, $v$ small. How make happen?
• Sampling! What's a good sample? (take suggestions, think about them.
• Define $G(p)$---pick each edge with probability $p$

Intuition:

• $G$ has $m$ edges, min-cut $c$
• $G(p)$ has $pm$ edges, min-cut $pc$
• So improve Gabow runtime by $p^2$ factor!

What goes wrong? (pause for discussion)

• expectation isn't enough
• so what, use chernoff?
  • min-cut has $c$ edges
  • expect to sample $\mu=pc$ of them
  • chernoff says prob. off by $\epsilon$ is at most $2e^{-\epsilon^2 \mu/4}$
  • so set $pc=8\log n$ or so, deduce with high probability, no min-cut deviates.
• (pause for objections)
• yes, a problem: exponentially many cuts.
• so even though Chernoff gives “exponentially small” bound, accumulation of union bound means can't bound probability of small deviation over all cuts.

Surprise! It works anyway.

• Theorem: if min cut $c$ and build $G(p)$, then “min expected cut” is $\mu=pc$. Probability any cut deviates by more than $\epsilon$ is $O(n^2 e^{-\epsilon^2 \mu/3})$.
  • So, if get $\mu$ around $12(\log n)/\epsilon^2$, all cuts within $\epsilon$ of expectation with high probability.
  • Do so by setting $p=12(\log n)/c$
• Application: min-cut approximation.
• Theorem says a min-cut will get value at most $(1+\epsilon)\mu$ whp
• Also says that any cut of original value $(1+\epsilon)c/(1-\epsilon)$ will get value at most $(1+\epsilon)\mu$
• So, sampled graph has min-cut at most $(1+\epsilon)\mu$, and whatever cut is minimum has value at most $(1+\epsilon)c/(1-\epsilon) \approx (1+2\epsilon)c$ in original graph.
• How find min-cut in sample? Gabow's algorithm
• in sample, min-cut $O((\log n)/\epsilon^2)$ whp, while number of edges is $O(m(\log n)/\epsilon^2 c)$
• So, Gabow runtime $\Olog(m/\epsilon^2 c)$
• constant factor approx in near linear time.

Proof of Theorem

• Suppose min-cut $c$ and build $G(p)$
• Lemma: bound on number of $\alpha$-minimum cuts is $n^{2\alpha}$.
  • Base on contraction algorithm
• So we take as given: number of cuts of value less than $\alpha c$ is at most $n^{2\alpha}$ (this is true, though probably slightly stronger than what you proved. If use $O(n^{2\alpha})$, get same result but messier.
• First consider $n^2$ smallest cuts. All have expectation at least $\mu$, so prob any deviates is $e^{-\epsilon^2 \mu/4} = 1/n^2$ by choice of $\mu$
• Write larger cut values in increasing order $c_1,\ldots$
• Then $c_{n^{2\alpha}} > \alpha c$
• write $k=n^{2\alpha}$, means $\alpha_k = \log k/\log n^2$
• What prob $c_k$ deviates? $e^{-\epsilon^2 pc_k/4} = e^{-\epsilon^2 \alpha_k \mu/4}$
• By choice of $\mu$, this is $k^{-2}$
• sum over $k>n^2$, get $O(1/n)$

Issue: need to estimate $c$.

Las Vegas:

• Tree pack sample? Note good enough: too few trees
• Partition into pieces, pack each one
• get $(1-\epsilon)\mu$ trees in each piece, so $(1-\epsilon)c$ total.
• So, run sampling alg till cut found and trees packed are within $\epsilon$.
• happens whp first time, repeat if not. Expected number of iterations less that 2, so poly expected time.

Idea for exact:

• Las vegas algorithm gave approximately maximum packing
• how turn maximum? Gabow augmentations.
• Idea: run approx alg for some $\epsilon$, then augment to optimum
• Gives faster algorithm.
• wait, faster algorithm could be used instead of Gabow's in approximation algorithm to get faster approximation algorithm
• then could use faster approx alg (followed by augmentations) to get faster exact algorithm
• each algorithms seems to imply a faster one
• What is limit? Recursive algorithm

DAUG:

• describe alg
• give recurrence: $T(m,c) = 2T(m/2,c/2)+\Olog(m\sqrt{c}) = \Olog(m\sqrt{c})$
• Are we done? (wait for comment)
• No! Subproblem sizes are random variables
• Wait, have used this trick in recurrences before
• But that was because recurrences were linear, could use linearity of expectation
• Here, recurrence nonlinear. Dead.

Recursion Tree:

• expand all nodes
• depth of tree $O(\log m)$ since unlikely to get 2 edges at same leaf
• wlog keep $n \le m$ by discarding isolated vertices
• successfull and unsuccessful augmentations
• telescoping of successful augmentations
• analyze “high nodes” where cut value near expectation
• analyze “low nodes” where cut values small (a fortiori) but rely mainly on having few edges.

Later work. Just talk about where this went.

• Linear time cut by tree packing
• applications to max-flow
• current state of affairs, open problems.

Reliability

Idea

• only small cuts matter
• enumerate them
• DNF count

Monte Carlo

• suppose $u_G(p)$ large
• Monte Carlo can estimate
• so assume $u_G(p)$ small

Small cuts

• $u_G(p) \ge p^c$
• so assume $p^c \le n^{-3}$
• show large cuts contribute much less
• before, we bounded $\alpha$-mincuts by $n^{2\alpha}$
• so in particular, $n^{2\alpha+2}$ cuts between $\alpha c$ and $(\alpha+1)c$
• contribution to $u_G(p)$ is at most $$ \begin{align*} n^{2\alpha+2}p^{\alpha c} &=n^{2\alpha+2}p^{3(\alpha-1)c}p^c\\ &=n^{2\alpha+2}n^{-3(\alpha-1)}p^c\\ &=n^{5-\alpha}p^c \end{align*} $$
• geometric sum over $\alpha$
• so dominated by first term
• if $\alpha > 6$, this is negligible.

Application

• enumerate small cuts using CA
• their failure probability is near $u_G(p)$
• pass to DNF counting algorithm
• get approximation to that

Alternative approach: coupling.

• a coupling of two random variables $X$ and $Y$ is a distribution over pairs $(X',Y')$ such that $X'$ has the same distribution as $X$ (so we needn't distinguish them) and $Y'$ has the same distribution as $Y$.
• what makes a coupling interesting is the dependencies we crate between the coupled $X$ and $Y$.
• for example, if every sample point from the joint distribution satisfier $X< Y$ then we have a proof that $Y$ stochstically dominates $X$
  • consider any value $t$
  • since $X< Y$, any sample point for which $Y< t$ also has $X< t$.
  • so $\Pr_{(X,Y)}[X< t] < \Pr_{(X,Y)}[Y< t]$
  • but $\Pr_{(X,Y)}[X< t] = \Pr_X[X< t]$ since we have a coupling
  • and similarly $\Pr_{(X,Y)}[Y< t] = \Pr_Y[X< t]$
  • so $\Pr[X< t]\le \Pr[Y< t] \forall t$.

which graph is least reliable, most likely to fail for given $n,c$?

• $n$ vertext cycle where each adjacent pair is connected by $c/2$ parallel edges
  • probability of disconnection is probability at least two “bundles” of $c/2$ edges fail.
  • each bundle fails with probability $p^{c/2}$
  • $n$ such bundles
  • number of failed bundles is $B(n.p^{c/2})$
  • failuer if this is not $0$ or $1$
  • so probability $1-(1-p^{c/2})^n-n(1-p^{c/2})^{n-1}p^{c/2}$
  • roughly $n^2p^c$ for small $p$
• coupling argument
  • For any $n$-vertex graph $G$ with min-cut $c$, generate $G(p)$ by deleting every edge of $G$ with probability $p$
  • Also generate $Y(p)$ for $Y$ the cycle of bundles described above
  • couple the random variables $G(p)$ and $Y(p)$ such that for every joint sample point where $G(p)$ is disconnected, $Y(p)$ is also disconnected
  • proves that $\Pr[G(p) \text{disconnected}] \le \Pr[Y(p) \text{disconnected}]$
• coupling
  • an unusual procedure to generate $G(p)$
    • $G$ has $m$ edges
    • decide how many edges $k$ of $G$ are not deleted ($B(m,1-p)$)
    • choose $k$ distinct edges at random, one at a time, from $G$ to form $G(p)$
    • we are only interested in whether resulting $G(p)$ is connected
    • so as we choose our edges, contract them
    • $G(p)$ is connected if the $k$ random contractions shrink $G$ to a single vertex
    • contractions can create self loops. keep them; they might get picked.
  • we will do the same for $Y(p)$, but coupled
    • every $G$ has at minimum degree $c$, so $m \ge nc/2$
    • $Y$ starts with exactly $nc/2$ edges
    • so can add self loops to $Y$, anywhere, so it also starts with $m$ edges total
    • doesn't change outcome since contracting self loops does nothing
    • in modified graph, we want to contract $B(m,1-p)$ edges (including new self loops)
    • contract same number $k$ of edges as $G$ (ie we couple the number of edges we are contracting)
    • before each contraction of $G$, create a pairing (matching) between uncontracted edges of $G$ and uncontracted edges of $Y$
    • when we choose our random edge of $G$ to contract, we also contract its match in $Y$
    • therefore, we are choosing a random edge of $Y$ to contract in each step, which makes our final distribution of $Y(p)$ correct
    • key fact: each contracted $Y$ is still a cycle of bundles!
  • the matching
    • design the matching at each step so contractions never make $Y$ have fewer vertices than $G$
    • conclude that if $G$ is disconnected at the end of contractions (more than one vertex) then so is $Y$
    • if in a step $Y$ has more vertices than $G$, matching can be arbitrary
    • one contraction shrinks $Y$ by at most 1. $G$ might not shrink, but at worst that means they end up the same size
    • harder case in a step where $G$ and $Y$ start at exactly same
    • by same arg as above that cycle has fewest edges, contracted $Y$ has no more non-self-loops than contracted $G$
    • so pair each non-self-loop of $Y$ to a non-self-loop of $G$
    • so if $Y$ shrinks because a non-self-loop gets contracted, so does $G$
    • so $Y$ cannot get smaller than $G$