$Ω((\log n/\log\log n)^2)$ Lower Bounds for Dynamic Graph Problems

Abstract

We prove an $Ω((\log n/\log\log n)^2)$ unconditional lower bound on the maximum of the update time and the query time for Pătraşcu's multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in $n$-node directed acyclic graphs under edge insertions, improving the $\widetildeΩ(\log^{3/2} n)$ lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem. The same bound holds for many other dynamic problems: in directed graphs, for incremental $s$-$t$ reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman's, Pagh's and Erickson's problems. Ko [FOCS 2026] recently proved this bound for a variant of the multiphase problem with Inner Product in place of Disjointness, via a 2.5-round multiphase communication game; we bring this framework to the original problem. Our main technical contribution is to show that verification in this game makes a one-sided corruption bound suffice in place of discrepancy, which Disjointness lacks.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.