TR16-167 Authors: Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

Publication: 1st November 2016 20:42

Downloads: 297

Keywords:

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) $.