Almost Perfect Bisection 2

This time I’m going to introduce <A polylogarithmic approximation of the minimum bisection> by Uriel Feige and Robert Krauthgamer. I will transfer my language to minimum bisection rather than maximum bisection, as they two transform to each other for obvious reason. This paper proved that if an $\epsilon$ minimum cut is guaranteed to exist, then the algorithm can find in poly-time another bisection cutting $O(\epsilon \log^2{n})$ (fraction of) edges. This is later improved to $O(\epsilon \log^{1.5}{n})$ because of the improved min-ratio cut algorithm by ARV.

The overall idea is to use divide-and-conquer. On each node of the divide-and-conquer tree (which is referred as the decomposition tree), the node set $V$ is split into $V=V_1 \cup V_2$. We want use a dynamic programming technique such that for node $V$ and a given $g$, find the min cut $V=C \cup F$ such that $|V|=g$. To obtain such we want to make use of the decomposition structure and two optimal solution $V_1=C_1 \cup F_1$ and $V_2=C_2 \cup F_2$, however, we have obstacles.

Notice that $Cut(C,F)=Cut(C_1,F_1)+Cut(C_2,F_2)+Cut(C_1,F_2)+Cut(C_2,F_1)$. With the third and fourth term, we cannot do divide-and-conquer easily. This paper provides an upper bound of the following form:
$Cut(C,F) \leq Cut(C_1,F_1) + Cut(C_2,F_2)+Cut(C_1,V_2)+Cut(C_2,V_1)$
If we call $Cut(C_1,V_2)+Cut(C_2,V_1)$ the extra terms, then instead of optimizing over the optimal cut, we optimize over the cut plus the extra terms. This can be done by dynamic programming after some complicated analysis.

We need to find an amortized cut.

For sure, it would be perfect if there exists some number $\rho$ s.t. $Cut(C_1,V_2) \leq \rho (C_1,F_1)$, but this won’t happen except the trivial case $\rho=n$. An easy solution to this is to amortize against $(C_1,F_1)$. This paper actually considered a double-amortization which also amortizes against $\frac{|C_1|}{|C|}\cdot edges(C,F)$. This is still not enough because we intend to find some overal $\rho$ that enables us to amortize over all possible cut $(C,F)$, including an optimal cut. This is another impossible mission so we instead amortize over all $(C,F)$ such that $0<|C|\leq \alpha |V|$ and $1/2 \leq \alpha < 1$ is a constant.

How to find such an amortized cut?

It can be proved that an optimal min-ratio cut for $V$ is a 2-amortized cut. However, since it is hard to compute the optimal one, an approximation subroutine has to be adopted. Assume that we have some $\tau$-approximate min-ratio cut algorithm (we actually had a $\tau=O(\sqrt{\log n})$ one), then one can easily find some $O(\tau)$-amortized cut. An arbitrary $\tau$-approximate min-ratio cut does not work, sadly; however, a maximized $\tau$-approximate cut does work. In details, we need a cut $(S,T)$ that is $\tau$ times smaller than the optimal cut, and for any subset of $S' \subset S, S'\neq S$, $(S', \bar{S'})$ is not a $\tau$ cut.

How to use such an amortized cut?

As it has been discussed above, the amortized cut will be used as the decomposition step for the divide-and-conquer algorithm. We need to do magic so that there exists a good enough bisection cut who always satisfies the $\alpha$ constraint.

Let us define a labelling of a decomposition tree. Each node set $V$ in the tree is labelled as either white or black. A labelling is $\alpha$-consistant with a global cut $(W,B)$ if and only if for each node $V$, $|W\cap V|\leq \alpha |V|$ if the node is white, and $|B\cap V|\leq \alpha |V|$ if the node is black. Then, for any global cut $(W,B)$ $\alpha$-consistant with the labelling, if we define either $C=W\cap V$ or $C=B\cap V$ accordingly (and $F=\bar{C}$), an observation (Lemma 10) is that the extra $Cut(C_1,V_2)+Cut(C_2,V_1)$ terms at each level of the decomposition tree sum up to at most $\rho \log{n} Cut(W,B)$.

This is a great lemma because if we consider the global optimal bisection cut $(W^*,B^*)$, then for a labelling that is consistant with it, the extra terms are $\rho \log{n}$ factor bounded. Then, as long as we find a good cut such that the extra terms are this amount bounded, we are happy: we have found a $\rho \log{n}$-approximation. This is done by defining a good family of labelings (though of exponential cardinality), which guarantees that the optimal bisection cut is inside that family (see Lemma 8).

One note about another paper

There exists another paper which uses a different embedding algorithm to create a $\log{n}$ approximation. I do not have time to talk about it. The basic idea is a general framework of embedding an arbitrary graph into a (random) tree, such that any commodity flow on the tree with congestion 1 admits a $\log{n}$ congestion when mapped to the graph. Then, the min bisection algorithm is just one of the applications of such embedding. One may refer to the paper <Optimal hierarchical decompositions for congestion minimization in networks> for details.