Sublinear Approximations for Spanning Tree Congestion

The spanning tree congestion of a connected graph \(G\) is the minimum, over all spanning trees \(T\) of \(G\), of the maximum number of edges of \(G\) crossing a cut induced by deleting an edge of \(T\). In the spanning tree congestion problem we are asked to compute a spanning tree with minimum congestion. We describe two sublinear-ratio approximation algorithms for the spanning tree congestion problem (STC): a simple (n8/9)-approximation, and a more involved (n2/3)-approximation, where the notation hides factors polynomial in log n.. Until now, no algorithm with sublinear ratio was known. We also prove that for any fixed 0<ε<1, approximation of the spanning tree congestion within 2-ε is NP-hard. This improves the previous best known lower bound $6/5$.