The purpose of this note is to present the seminal paper by Klein, Plotkin and Rao [1].
We prove the following theorem. The proof is not really different from the original proof, I just tried to remove all the details that were not necessary, and reformulate the useful ideas in a way that I find more intuitive. James Lee gave a short proof of this theorem at a workshop in Banff in December 2011 , but I can't remember the details.
Theorem 1: (Klein , Plotkin, Rao [1]) Given a graph $G$, two parameters $\delta$ and $r$, then we can either find a $K_{r,r}$ minor in $G$, or find a decomposition of $G$ into components $C_1,\ldots,C_k$ such that :
Proof: The main ingredient in the proof is the construction of the decomposition. This is done by using successive breadth-first-search (BFS) in smaller and smaller parts of the graph.
Let $G_0 = G$, and define iteratively $G_{i+1}$ from $G_i$, if $G_i$ has diameter greater than $4 \delta r(r+1)$, by the following construction. Choose an arbitrary vertex $r_i$ in $G_i$, and let $\mathcal{T}_i$ be a BFS tree from $r_i$. Then choose some value $l$ and take $V_{i+1} = \left\{v \in V(G_i) : d_{G_i}(r_i,v) \in [l, l+ \delta -1]\right\}$, and let $G_{i+1}$ be a component of $G[V_{i+1}]$. Hence $G_{i+1}$ is a component of the graph induced by $\delta$ consecutive layers in $\mathcal{T}_i$. The main lemma in the original proof is the following:
Lemma 2: (Klein , Plotkin, Rao [1]) If $G_{r+1}$ exists and there is $u,v \in V(G_{r+1})$ such that $d_G(u,v) \geq 4 \delta r (r+1)$, then there is a $K_{r,r}$-minor in $G$ (and we can find it algorithmically).
Proof: Assume wlog $r \geq 2$. We prove the following by iterating on $i$ from $r+1$ to $1$: there is a $K_{r+1-i,r}$-minor in $G_i$. In addition, denote $S^i_j, j\in \{i,\ldots,r\}$ and $T^i_j, j \in \{1,\ldots,r\}$ the supernodes of the minor. Then we also assume that there is $u^i_j \in T^i_j$ for all $i \in \{1,\ldots,r\}$ with the properties:
The base case is when $i=r+1$, then by assumption there is $u,v$ and a $(u,v)$-path in $G_r$ of length at least $4 \delta r (r+1)$ (because $d_G(u,v) \geq 4 \delta r (r+1)$ and the distance are longer in $G_r$). Clearly one can choose $r$ vertices at distance $4 \delta (r+1)$ from each other on this path. This defines $u^{r+1}_1$ to $u^{r+1}_r$, and by partitioning the path we get $T^{r+1}_1$ to $T^{r+1}_r$ as wanted.
Now suppose that we have iteratively built the $K_{r+1-i,r}$-minor in $G_{i+1}$, for $i \in \{1,\ldots, r-1\}$. For each $j \in \{1,\ldots,r\}$, define $P^i_j$ as the unique directed path in $\mathcal{T}_i$ from the root to $u^{i+1}_j$. Such a path has length at least $(2 r (r+1) -1) \delta > 4 \delta$ (otherwise vertices of $G_r$ would be at distance at most $2 \delta r(r+1)$ from $r_i$ in $G$, contradicting the assumption). Define:
We check the hypothesis. Firstly, by the triangle inequality,
$$ \begin{align*} d_G(u^i_j,u^i_k) &\geq d_G(u^{i+1}_j,u^{i+1}_k) - d_G(u^i_j,u^{i+1}_j) - d_G(u^i_k,u^{i+1}_k) \\ &\geq 4 \delta (i+1)- 2 \delta - 2 \delta \\ &\geq 4 \delta i \end{align*} $$
Then by construction, $u^i_j$ is at distance more than $\delta$ from $G_{i+1}$ and from $S^i_i$ in $G_i$ (we used a path in a BFS tree), and at distance (in $G_i$) at least $4 \delta$ from any $u^i_k$, $k \neq j$. Hence $u^i_j$ is at distance more than $\delta$ in $G_i$ to any supernode except $T^i_j$.
It remains to check that it gives indeed a $K_{r+1-i,r}$ minor. Most of it is clear by construction, the hard part is to prove the disjointness of the supernodes. The only not-obvious part is for what happen in $G_{i+1}$ when we add the $P^i_j$ to the previous supernodes. But then, because $u^{i+1}_j$ is at distance more than $\delta$ in $G_{i+1}$ from any other supernode by hypothesis, $P^i_j$ is disjoint from any supernode from level $i+1$ except $T^{i+1}_j$.
Given a graph $G$, let $R$ be a set of vertices intersecting each component of $G$ exactly once. Define $E_0,\ldots, E_{\delta-1}$, with $E_i = \left\{(u,v) : 2 \delta r^2 \leq d(R,v) - 1 = d(R,u) \equiv i \pmod{\delta} \right\}$ (hence it is the union of edge sets between two levels of a BFS, every $l$ levels). These sets are disjoint, $\sum_{i=0}^{\delta-1} E_i \subset E(G)$ hence there is $\iota$ such that $\left|E_\iota\right| \leq \left|E(G)\right| / \delta$. Define an elementary clustering of $G$ as the graph $G' = G \setminus E_\iota$. Then each connected component $C$ of $G'$ has either diameter $4 \delta r(r+1)$ (in particular the component containing $r$), or has $\{d(r,v) : v \in V(C)\} \subseteq \left[l,l+\delta-1\right]$ for some $l$.
As a consequence, for any graph $G$, after $r$ successive operations of elementary clustering, by Lemma 2,
Moreover this construction can be implemented using breadth-first-search in polynomial-time.
Any graph $F$ is a minor of $K_{r,r}$ for some $r = r(F)$ big enough. Hence Theorem 1 is a decomposition theorem for any forbidden-minor class of graphs. We use this to prove that the flow-cut gap of any such class is constant. First we recall some definition.
A multicommodity flow instance is a pair of graphs $G,H$ on a common set of vertices $V(G)$, together with a capacity function $c: E(G) \to \mathbb{N}$ and a demand function $D: E(H) \to \mathbb{N}$. A solution is a family $(f_h)_{h \in E(H)}$ of flows indexed by the demand edges $E(H)$, such that:
The throughput of a solution is defined by $\min_h \left|f_H\right|/D_h$. The Maximum Throughput problem is: given a multicommodity flow instance, find a solution maximizing its throughput.
An easy way to bound the maximum throughput, denoted by $\tau$, is to find a bottleneck in the graph, which is a cut such that the demand through it is larger than its capacity. We define:
$$ \Gamma = \min_{U \subset V : D(\delta_H(U)) > 0} \frac{c(\delta_G(U))}{D(\delta_H(U))}$$
and we have $\tau \leq \Gamma$. The flow-cut gap for $G,H,c,D$ is defined by $\frac{\Gamma}{\tau}$.
A harder but optimal way to bound the maximum throughput is given by the so-called Japanese Theorem, which is an immediate consequence of linear duality:
Theorem 3: $ \tau = \min_{l} \sum_{e \in E(G)} c_e \cdot l_e $ where the minimum is taken over all $l : E(G) \to \mathbb{Q}_+$ such that $\sum_{h = st \in E(H)} D_H \cdot d_l(s,t) = 1$.
We actually want to work with $l$ integral values, hence by scaling we rewrite it as
$$ \tau = \min_{0 \neq l \in \mathbb{N}^{E(G)}} \frac{\sum_{e \in E(G)} c_e \cdot l_e}{\sum_{h = st \in E(H)} D_H \cdot d_l(s,t)} $$
Theorem 4: Let $G,H,c,D$ be some multicommodity flow instance, such that $H$ does not contain a $K_{r,r}$-minor, and define $\Gamma$, $\tau$ and $l$ as above. Then the flow-cut gap is at most $2 r^2(r+1) \log D(E(H))$
Proof: Fix a parameter $\delta = \frac{r \cdot c(E(G))}{\Gamma \cdot D(E(H))}$ and apply Theorem 1 to $G,c,l$ (note how $c$ can be encoded by parallel edges, and $l$ by series edges), to get a decomposition of $G$ into components $C_1,\ldots,C_k$ with:
Consider first the demands between distinct components among $C_1,\ldots,C_k$. By definition of $\Gamma$, for a component $C_i$ we have
$$ \sum_{st \in \delta_H(C_i)} D(st) \leq \frac{c(\delta(C_i))}{\Gamma}$$
Then by summing over all components:
$$ \sum_{i \neq j} \sum_{st \in E[C_i,C_j]} D(st) \leq \frac{1}{2 \Gamma} \sum_{i} c(\delta(C_i)) \leq \frac{r}{2 \Gamma \cdot \delta} c(E(G)) = \frac{1}{2} D(E(H)) $$
Here the second inequality comes from the properties of the decomposition. Hence at least half of the demand is contained in components of diameter $4 \delta r(r+1)$ in $G$. We deduce:
$$ \sum_i \sum_{st \in C_i} D(st) d_l(s,t) \leq 4 \delta r(r+1) \cdot \frac{1}{2} D(E(G)) = 2 r^2(r+1) \frac{C(E(G))}{\Gamma} $$
Now, by applying recursively this argument to the instance $G,H',c,D'$, where $H',D'$ are obtained from $H,D$ by removing all the demands internal to some component $C_i$ of the decomposition, we get that
$$ \sum_{st \in E(H)} D(st) d_l(s,t) \leq 2 \delta r^2(r+1) \frac{C(E(G))}{\Gamma} \log D(E(H)) $$
Using this in the flow-cut gap formula we get:
$$\frac{\Gamma}{\tau} = \Gamma \cdot \frac{\sum_{st \in E(H)} D(st) d_l(s,t)}{\sum_{e \in E(G)} c_e \cdot l_e} \leq 2 r^2 (r+1) \log D(E(H))$$
| 1. | , , : Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the twenty-fifth annual ACM Symposium on Theory of Computing. , 682 -- 690. (1993). |
