Klein, Plotkin, Rao

The purpose of this note is to present the seminal paper by Klein, Plotkin and Rao [1].

Clustering of graphs with no $K_{r, r}$ minor

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 $δ$ and $r$ , then we can either find a $K_{r, r}$ minor in $G$ , or find a decomposition of $G$ into components $C_{1}, \dots, C_{k}$ such that :

for any $i$ and any $u, v \in C_{i}$ , $d_{G} (u, v) \leq 4 δ r (r + 1)$ ,
$\sum_{i \neq j} | E [C_{i}, C_{j}] | \leq \frac{r}{δ} | E (G) |$

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 δ r (r + 1)$ , by the following construction. Choose an arbitrary vertex $r_{i}$ in $G_{i}$ , and let $T_{i}$ be a BFS tree from $r_{i}$ . Then choose some value $l$ and take $V_{i + 1} = {v \in V (G_{i}) : d_{G_{i}} (r_{i}, v) \in [l, l + δ - 1]}$ , 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 $δ$ consecutive layers in $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 δ 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_{j}^{i}, j \in {i, \dots, r}$ and $T_{j}^{i}, j \in {1, \dots, r}$ the supernodes of the minor. Then we also assume that there is $u_{j}^{i} \in T_{j}^{i}$ for all $i \in {1, \dots, r}$ with the properties:

$d_{G} (u_{j}^{i}, u_{k}^{i}) \geq 4 i δ$ for all $j \neq k$ ,
$u_{j}^{i}$ is at distance more than $δ$ in $G_{i}$ from any other supernode.

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 δ r (r + 1)$ (because $d_{G} (u, v) \geq 4 δ r (r + 1)$ and the distance are longer in $G_{r}$ ). Clearly one can choose $r$ vertices at distance $4 δ (r + 1)$ from each other on this path. This defines $u_{1}^{r + 1}$ to $u_{r}^{r + 1}$ , and by partitioning the path we get $T_{1}^{r + 1}$ to $T_{r}^{r + 1}$ as wanted.

Now suppose that we have iteratively built the $K_{r + 1 - i, r}$ -minor in $G_{i + 1}$ , for $i \in {1, \dots, r - 1}$ . For each $j \in {1, \dots, r}$ , define $P_{j}^{i}$ as the unique directed path in $T_{i}$ from the root to $u_{j}^{i + 1}$ . Such a path has length at least $(2 r (r + 1) - 1) δ > 4 δ$ (otherwise vertices of $G_{r}$ would be at distance at most $2 δ r (r + 1)$ from $r_{i}$ in $G$ , contradicting the assumption). Define:

$u_{j}^{i}$ to be the vertex at distance $2 δ$ from $u_{j}^{i + 1}$ on $P_{j}^{i}$ .
$T_{j}^{i} = T_{j}^{i + 1} \cup Q_{j}^{i}$ where $Q_{j}^{i}$ is the subpath of $P_{j}^{i}$ of length $4 δ$ , starting from $u_{j}^{i + 1}$ ,
$S_{i}^{i} = ⋃_{j} P_{j}^{i} ∖ Q_{j}^{i}$ ,
$S_{j}^{i} = S_{j}^{i + 1}$ for any $j \in {i + 1, \dots, r}$ .

We check the hypothesis. Firstly, by the triangle inequality,

$\begin{aligned} d_{G} (u_{j}^{i}, u_{k}^{i}) & \geq d_{G} (u_{j}^{i + 1}, u_{k}^{i + 1}) - d_{G} (u_{j}^{i}, u_{j}^{i + 1}) - d_{G} (u_{k}^{i}, u_{k}^{i + 1}) \\ \geq 4 δ (i + 1) - 2 δ - 2 δ \\ \geq 4 δ i \end{aligned}$

Then by construction, $u_{j}^{i}$ is at distance more than $δ$ 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 δ$ from any $u_{k}^{i}$ , $k \neq j$ . Hence $u_{j}^{i}$ is at distance more than $δ$ in $G_{i}$ to any supernode except $T_{j}^{i}$ .

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_{j}^{i}$ to the previous supernodes. But then, because $u_{j}^{i + 1}$ is at distance more than $δ$ in $G_{i + 1}$ from any other supernode by hypothesis, $P_{j}^{i}$ is disjoint from any supernode from level $i + 1$ except $T_{j}^{i + 1}$ .

Given a graph $G$ , let $R$ be a set of vertices intersecting each component of $G$ exactly once. Define $E_{0}, \dots, E_{δ - 1}$ , with $E_{i} = {(u, v) : 2 δ r^{2} \leq d (R, v) - 1 = d (R, u) \equiv i (\mod δ)}$ (hence it is the union of edge sets between two levels of a BFS, every $l$ levels). These sets are disjoint, $\sum_{i = 0}^{δ - 1} E_{i} \subset E (G)$ hence there is $ι$ such that $| E_{ι} | \leq | E (G) | / δ$ . Define an elementary clustering of $G$ as the graph $G^{'} = G ∖ E_{ι}$ . Then each connected component $C$ of $G^{'}$ has either diameter $4 δ r (r + 1)$ (in particular the component containing $r$ ), or has ${d (r, v) : v \in V (C)} \subseteq [l, l + δ - 1]$ for some $l$ .

As a consequence, for any graph $G$ , after $r$ successive operations of elementary clustering, by Lemma 2,

either we find a $K_{r, r}$ minor,
or for each remaining component $C$ , for each $u, v \in V (C)$ , $d_{G} (u, v) \leq 4 δ r (r + 1)$ , and we removed at most $\frac{r}{δ} | E (G) |$ edges.

Moreover this construction can be implemented using breadth-first-search in polynomial-time.

Flow-cut gap in minor-closed classes of graphs

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 N$ and a demand function $D : E (H) \to N$ . A solution is a family $(f_{h})_{h \in E (H)}$ of flows indexed by the demand edges $E (H)$ , such that:

$f_{h}$ is an $(s, t)$ -flow, where $h = s t \in E (H)$ , and $| f_{h} | \leq D_{h}$ ( $| f_{H} |$ denotes the value of the flow),
$\sum_{h \in E (H)} f_{h} \leq c$ .

The throughput of a solution is defined by $min_{h} | f_{H} | / 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 $τ$ , 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:

$Γ = min_{U \subset V : D (δ_{H} (U)) > 0} \frac{c (δ_{G} (U))}{D (δ_{H} (U))}$

and we have $τ \leq Γ$ . The flow-cut gap for $G, H, c, D$ is defined by $\frac{Γ}{τ}$ .

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: $τ = min_{l} \sum_{e \in E (G)} c_{e} \cdot l_{e}$ where the minimum is taken over all $l : E (G) \to Q_{+}$ such that $\sum_{h = s t \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

$τ = min_{0 \neq l \in N^{E (G)}} \frac{\sum_{e \in E (G)} c_{e} \cdot l_{e}}{\sum_{h = s t \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 $Γ$ , $τ$ 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 $δ = \frac{r \cdot c (E (G))}{Γ \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}, \dots, C_{k}$ with:

for any $u, v \in C_{j}$ , $d_{l} (u, v) \leq 4 δ r (r + 1)$ ,
$\sum_{i \neq j} c (E [C_{i}, C_{j}]) \leq \frac{c (E (G)) \cdot r}{δ}$ .

Consider first the demands between distinct components among $C_{1}, \dots, C_{k}$ . By definition of $Γ$ , for a component $C_{i}$ we have

$\sum_{s t \in δ_{H} (C_{i})} D (s t) \leq \frac{c (δ (C_{i}))}{Γ}$

Then by summing over all components:

$\sum_{i \neq j} \sum_{s t \in E [C_{i}, C_{j}]} D (s t) \leq \frac{1}{2 Γ} \sum_{i} c (δ (C_{i})) \leq \frac{r}{2 Γ \cdot δ} 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 δ r (r + 1)$ in $G$ . We deduce:

$\sum_{i} \sum_{s t \in C_{i}} D (s t) d_{l} (s, t) \leq 4 δ r (r + 1) \cdot \frac{1}{2} D (E (G)) = 2 r^{2} (r + 1) \frac{C (E (G))}{Γ}$

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_{s t \in E (H)} D (s t) d_{l} (s, t) \leq 2 δ r^{2} (r + 1) \frac{C (E (G))}{Γ} \log D (E (H))$

Using this in the flow-cut gap formula we get:

$\frac{Γ}{τ} = Γ \cdot \frac{\sum_{s t \in E (H)} D (s t) d_{l} (s, t)}{\sum_{e \in E (G)} c_{e} \cdot l_{e}} \leq 2 r^{2} (r + 1) \log D (E (H))$

Philip Klein, Serge A. Plotkin, Satish Rao: Excluded minors, network decomposition, and multicommodity flow.
In: Proceedings of the twenty-fifth annual ACM Symposium on Theory of Computing. , 682 -- 690.
(1993).