$\Omega ((\log n/\log \log n{)}^2)$ Lower Bounds for Dynamic Graph Problems

Abstract

We prove an $\Omega ((\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 $\tilde{\Omega }({\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.

arXiv comment33 pages, 1 figure. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised