Super-Logarithmic Lower Bounds for Dynamic Graph Problems

In this work, we prove a $\tilde{\Omega}(\lg^{3/2} n)$ 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 is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.

Authors

• Kasper Green Larsen
• Huacheng Yu

Keywords

• Computer science
• Directed acyclic graph
• Heuristic algorithms
• Computational modeling
• Data structures
• Lower Bound
• Dynamic Problem
• Graph Problems
• Data Structure
• Structural Dynamics
• Update Time
• Query Time
• Posterior Probability
• State Structures
• Memory Cells
• Butterfly
• Product Distribution
• Efficient Data
• Nodes In Layer
• Information Bits
• Static Problem
• Number Of Probes
• Proof Of The Lemma
• One-way Communication
• Decoding Procedure
• cell-probe model
• data structure lower bounds
• dynamic reachability
• dynamic graph algorithms