Flows in High Degree Places: Sublinear Spanning Tree Congestion

The congestion of a spanning tree T of graph G is the maximum congestion of an edge of T if each edge of G is routed on T. Prior work showed that obtaining a minimum congestion spanning tree is NP-hard to approximate within $6/5$, yet the only known approximation algorithm is a trivial $n/2$-approximation from returning any spanning tree of the graph. We give a simple poly-time Õ(n6/7)-approximation for minimum congestion spanning tree on n-vertex graphs. We obtain this result via a Õ(m2/3)-approximation, where m is the number of edges. Our algorithm is based on a new flow-or-degree decomposition which deletes a small number of edges so that each remaining component either has low degree or admits a low congestion flow. We also show that, assuming the Small Set Expansion Hypothesis, it is NP-hard to $O(1)$-approximate this problem, even on graphs of constant maximum degree.