Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-244 | 9th October 2026 21:45

?((log n/log log n)²) Lower Bounds for Dynamic Graph Problems

RSS-Feed




TR26-244
Authors: Young Kun Ko
Publication: 10th October 2026 09:49
Downloads: 17
Keywords: 


Abstract:

We prove an $\Omega((\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{\Omega}(\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 [STOC 2010] 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.



ISSN 1433-8092 | Imprint