Fully Dynamic Edge Connectivity in $\tilde{O}(n^{12/13})$ Time
2026-07-12 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where a graph changes over time by adding or removing edges, and the goal is to keep track of how connected the graph is. They create a new randomized method that can quickly update and answer questions about connectivity for any graph, doing better than previous methods that only worked well for certain cases. They also design two other deterministic algorithms: one improves update and query speed significantly, and the other works on more complex graphs called multigraphs. Overall, the authors improve how fast we can handle changing networks and measure their connectivity.
dynamic graph algorithmsedge connectivityrandomized algorithmdeterministic algorithmupdate timequery timesimple graphmultigraphamortized complexityworst-case complexity
Authors
Yotam Kenneth-Mordoch, Robert Krauthgamer
Abstract
In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity $λ_G$ of an $n$-vertex graph $G$ that undergoes edge insertions and deletions. Our main result is a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\tilde{O}(n^{12/13})$, for all values of $λ_G$. This is the first algorithm that has $o(n)$ update and query time, as all existing algorithms achieve this only when $λ_G$ is below $n^{1/11}$ or above $n^{1/2}$ (up to polylogarithmic factors). We then use the tools developed for this purpose to design two additional algorithms. The first one is a deterministic algorithm for the exact same task, that uses $n^{1+o(1)}$ worst-case update and query time or $\tilde{O}(n)$ amortized update and query time; this gives a polynomial improvement over existing deterministic algorithms. The second one is a deterministic algorithm for the same task but in dynamic unweighted multigraphs, that uses $\tilde{O}(n^{3/2})$ worst-case update and query time.