Dynamic graph problem update and query times must grow squared log ratio
$Ω((\log n/\log\log n)^2)$ Lower Bounds for Dynamic Graph Problems
Data Structures and AlgorithmsComputational Complexity
Summary
This paper shows that when you change parts of certain directed graphs and try to quickly answer if one part connects to another, there's a fundamental speed limit to how fast this can be done. The researchers improved previous knowledge about these speed limits, showing they're even stricter than known before. Their proof uses advanced ideas from communication theory to handle specific graph problems better. This tells computer scientists that some fast answers for dynamic graphs just aren't possible.
What this means in practice
- •For database engineers: Understand intrinsic speed limits when updating and querying graph databases to set realistic performance expectations.
- •For network protocol designers: Recognize fundamental delays in dynamically managing network connectivity information to guide design of routing algorithms.
A theory result. No direct application yet.
Authors
Young Kun Ko
Abstract
We prove an $Ω((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions. This improves the $\widetildeΩ(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matches the strongest lower bound known for any dynamic problem. The same bound holds for incremental undirected shortest paths and subgraph connectivity. To prove it, we bring the recent framework of Ko [FOCS 2026], which gave this bound for Pătraşcu's multiphase problem with Inner Product, to the multiphase problem with Disjointness. Our main technical contribution is to show that verification in Ko's 2.5-round multiphase communication game makes a one-sided corruption bound suffice in place of discrepancy, which Disjointness lacks.