Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams

View PDF

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees (MSTs). These results have since been improved or generalized in various directions, leading to a vastly rich host of efficient algorithms for processing dynamic graph streams.
A curious omission from the list of improvements has been the MST problem. The best algorithm for this problem remains the original AGM algorithm that for every integer p≥1, uses n1+O(1/p) space in p passes on n-vertex graphs, and thus achieves the desired semi-streaming space of O~(n) at a relatively high cost of O(lognloglogn) passes. On the other hand, no lower bounds beyond a folklore one-pass lower bound is known for this problem.
We provide a simple explanation for this lack of improvements: The AGM algorithm for MSTs is optimal for the entire range of its number of passes! We prove that even for the simplest decision version of the problem -- deciding whether the weight of MSTs is at least a given threshold or not -- any p-pass dynamic streaming algorithm requires n1+Ω(1/p) space. This implies that semi-streaming algorithms do need Ω(lognloglogn) passes.
Our result relies on proving new multi-round communication complexity lower bounds for a variant of the universal relation problem that has been instrumental in proving prior lower bounds for single-pass dynamic streaming algorithms. The proof also involves proving new composition theorems in communication complexity, including majority lemmas and multi-party XOR lemmas, via information complexity approaches.