Optimal Multi-pass Lower Bounds for MST in Dynamic Streams

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 n 1`Op1pq space in p passes on n-vertex graphs, and thus achieves the desired semi-streaming space of r Opnq at a relatively high cost of Op log n log log n q 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 n 1`Ωp1pq space. This implies that semi-streaming algorithms do need Ωp log n log log n q 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.