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

Preprint · Young Kun Ko

- Archive id: arxiv:2610.10904
- Published: 2026-10-07
- arXiv: https://arxiv.org/abs/2610.10904
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.10904
- PDF: https://arxiv.org/pdf/2610.10904
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.