Improved method finds better low-congestion spanning trees in graphs
Flows in High Degree Places: Sublinear Spanning Tree Congestion
Data Structures and Algorithms
Summary
The paper deals with finding the best way to connect all points in a network with a tree where no single connection gets too overloaded. This problem is hard to solve perfectly, and past solutions were very rough. The authors found a new method that gives much better approximations efficiently in large networks by cleverly breaking the network into parts with simpler structures. They also proved it remains very hard to get even close to the best solution in certain cases.
What this means in practice
- •For network engineers: Optimize network link usage by finding spanning trees that reduce maximum congestion in communication networks.
- •For infrastructure planners: Design more efficient infrastructural connections minimizing bottlenecks by approximating low-congestion spanning trees in large graphs.
A theory result. No direct application yet.
Authors
D Ellis Hershkowitz, Richard Z Huang
Abstract
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 $\tilde{O}(n^{6/7})$-approximation for minimum congestion spanning tree on $n$-vertex graphs. We obtain this result via a $\tilde{O}(m^{2/3})$-approximation, where $m$ is the number of edges. Our algorithm is based on a new \textit{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.