Approximation of Spanning Tree Congestion using Hereditary Bisection

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∈ 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(Δ·log3/2n)-approximation algorithm where $Δ$ 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)≥ Ω(hb(G)/Δ). Final DMTCS version. 9 pages