Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-167 | 1st November 2016 18:07

New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity


Authors: Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
Publication: 1st November 2016 20:42
Downloads: 297


The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst case update time of a data structure for connectivity on graphs of size $n$. We prove the following,
- For every $\delta>0$ and any data structure for connectivity with error at most $\frac{1}{4n^\delta}$, if $t_u = o\left( \frac{\log n}{\log \log n}\right)$, then $t_q \geq \Omega\left( \delta n^{1-3\delta} \right)$. Patrascu and Thorrup in [PT11] show the same for data structures with zero errors.

In addition, we simplify the proof of dynamic connectivity lower bound established in the landmark paper of Fredman and Saks[FS89]. The result states that for any data structure for connectivity with constant error bounds, $t_q \geq \Omega\left( \frac{\log n}{\log (w+\log n)t_u}\right) $.

ISSN 1433-8092 | Imprint