Spanning Tree Congestion and Computation of Generalized Gy\H{o}ri-Lov{\'{a}}sz Partition.

We study a natural problem in graph sparsification, the Spanning TreeCongestion (\STC) problem. Informally, the \STC problem seeks a spanning treewith no tree-edge \emph{routing} too many of the original edges. The root ofthis problem dates back to at least 30 years ago, motivated by applications innetwork design, parallel computing and circuit design. Variants of the problemhave also seen algorithmic applications as a preprocessing step of severalimportant graph algorithms.

For any general connected graph with $n$ vertices and $m$ edges, we show thatits STC is at most $\mathcal{O}(\sqrt{mn})$, which is asymptotically optimalsince we also demonstrate graphs with STC at least $\Omega(\sqrt{mn})$. Wepresent a polynomial-time algorithm which computes a spanning tree withcongestion $\mathcal{O}(\sqrt{mn}\cdot \log n)$. We also present anotheralgorithm for computing a spanning tree with congestion$\mathcal{O}(\sqrt{mn})$; this algorithm runs in sub-exponential time when $m =\omega(n \log^2 n)$.

For achieving the above results, an important intermediate theorem is\emph{generalized Gy\H{o}ri-Lov{\'{a}}sz theorem}, for which Chen et al. gave anon-constructive proof. We give the first elementary and constructive proof byproviding a local search algorithm with running time $\mathcal{O}^*\left( 4^n\right)$, which is a key ingredient of the above-mentioned sub-exponential timealgorithm. We discuss a few consequences of the theorem concerning graphpartitioning, which might be of independent interest.

We also show that for any graph which satisfies certain \emph{expandingproperties}, its STC is at most $\mathcal{O}(n)$, and a corresponding spanningtree can be computed in polynomial time. We then use this to show that a randomgraph has STC $\Theta(n)$ with high probability.