New algorithms reduce congestion in connecting network graphs

Sublinear Approximations for Spanning Tree Congestion

Data Structures and Algorithms

Summary

Spanning tree congestion measures how crowded connections get when linking all points in a network using a tree structure. The authors developed new methods that find ways to connect all points with less congestion, improving on previous approaches that couldn't guarantee much better than the worst case. Their algorithms approximate the minimum congestion much more efficiently than before, and they also show it's very hard to find near-perfect solutions quickly. This work helps understand limits and possibilities for optimizing network connections.

What this means in practice

  • For network engineers: Design network backbones with lower maximum traffic bottlenecks by using approximation algorithms to find better spanning trees in large graphs.
  • For distributed systems developers: Improve communication efficiency by constructing spanning trees that limit congestion points in overlay or distributed networks.

A theory result. No direct application yet.

Authors

Sunny Atalig, Marek Chrobak, Petr Kolman, Hans Raj Tiwary

Abstract

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 $\Ot(n^{8/9})$-approximation, and a more involved $\Ot(n^{2/3})$-approximation, where the notation $\Ot$ hides factors polynomial in $\log n$.. Until now, no algorithm with sublinear ratio was known. We also prove that for any fixed $0<\varepsilon<1$, approximation of the spanning tree congestion within $2-\varepsilon$ is NP-hard. This improves the previous best known lower bound $6/5$.