Spanning Tree Congestion and the Generalized Győri-Lovász Theorem (Part 1)

We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, the STC problem seeks a spanning tree such that no tree-edge routes too many of the original edges. The root of this problem dates back to at least 30 years ago, with motivations from applications in network design, parallel computing and circuit design. Variants of the problem have also seen great algorithmic applications as a preprocessing step of several important graph algorithms.

We focus on three scenarios: (a) general connected graphs with $n$ vertices and $m$ edges, (b) random graphs and (c) graphs with very high minimum degree. For all these scenarios, we prove tight bounds on the spanning tree congestion (STC). For (a), we show that the STC is at most $\O(\sqrt{mn})$. We present an algorithm for computing such a spanning tree, which runs in sub-exponential time when $m = \omega(n \log^2 n)$. We also demonstrate graphs with STC at least $\Omega(\sqrt{mn})$. For (b) and (c), we prove that the STC are $\Theta(n)$ (with high probability) and $\Theta(n)$ respectively, and we present constant-approximation polynomial time algorithms that compute such a spanning tree.

For establishing these results, an important intermediate theorem is a generalization of the Győri-Lovász theorem. The classical Győri-Lovász theorem was proved in the 1970's, which states: for any $k$-vertex-connected graph $G=(V,E)$, $k$ distinct terminal vertices $t_1,\cdots,t_k$, and $k$ positive integers $n_1,\cdots,n_k$ which sum to $|V|$, there always exists a partition of $V$ into $k$ sets, such that (i) the $j$-th set contains the terminal $t_j$; (ii) the cardinality of the $j$-th set is exactly $n_j$; and crucially, (iii) each set induces a \emph{connected} subgraph. In this paper, we prove a natural generalization of this theorem, in which the vertices have positive real weights, and the partitioning requirement is on the sum of vertex weights in each set. We present an $\Os\left( 4^n \right)$ algorithm for finding such a partition; if we need only $k/2$ sets instead of $k$, the algorithm's running time improves to $\Os(2^{\O((n/k)\log k)})$.

The generalized Győri-Lovász theorem implies the following result concerning graph partitioning: for any $k$-vertex-connected graph with $m$ edges, there exists a $k$-partition that satisfies (i) and (iii), and the number of edges leaving each set is at most $4m/k$, which is optimal up to a constant factor.