Approximation of Spanning Tree Congestion using Hereditary Bisection

Abstract

The Spanning Tree Congestion (STC) problem is the following NP-hard problem: given a graph $G$, construct a spanning tree $T$ of $G$ minimizing its maximum edge congestion where the congestion of an edge $e\in T$ is the number of edges $uv$ in $G$ such that the unique path between $u$ and $v$ in $T$ passes through $e$; the optimal value for a given graph $G$ is denoted $STC(G)$. It is known that every spanning tree is an $n/2$-approximation for the STP problem. A long-standing problem is to design a better approximation algorithm. Our contribution towards this goal is an $O(\hat{I}”\cdot {\log }^{3/2}n)$-approximation algorithm where $\hat{I}”$ is the maximum degree in $G$ and $n$ the number of vertices. For graphs with a maximum degree bounded by a polylog of the number of vertices, this is an exponential improvement over the previous best approximation. Our main tool for the algorithm is a new lower bound on the spanning tree congestion which is of independent interest. Denoting by $hb(G)$ the hereditary bisection of $G$ which is the maximum bisection width over all subgraphs of $G$, we prove that for every graph $G$, $STC(G)\ge \hat{I}\text{c◯}(hb(G)/\hat{I}”)$.

Final DMTCS version. 9 pages