Fast graph algorithms maintain connectivity and spanning trees instantly

Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time

Data Structures and Algorithms

Summary

Graphs show how things are connected, like roads between cities or friends in a network, and keeping track of changes quickly is important. The authors developed fast algorithms that update key graph properties, like whether everything stays connected or finding the cheapest way to link all points, even when connections change. These algorithms work quickly in the worst case and use randomness in a limited way that makes them reliable against tricky situations. This improves on previous approaches that were slower for certain problems.

What this means in practice

  • For network engineers: Maintain network connectivity and routing maps efficiently as links fail or are added in real-time.
  • For distributed system builders: Quickly adapt system-wide data structures that depend on graph connectivity for fault tolerance and load balancing.

A theory result. No direct application yet.

Authors

Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh

Abstract

We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and $2$-edge connectivity of a graph with worst-case polylogarithmic update time. Our algorithms are randomized and succeed with high probability against an adaptive adversary. For the minimum spanning tree and $2$-edge connectivity problems, this improves over the subpolynomial update time bounds obtained by Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17], Jin and Sun [FOCS'21], and Jin, Sun, and Thorup [SODA'24], respectively. The only randomized component of our algorithms is the computation of static expander decompositions, and a deterministic algorithm for said problem would directly imply deterministic algorithms for all three problems. This reduction is novel even for the connectivity problem.