Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-167 | 8th June 2017 00:42

Simplified Data Structure Lower Bounds for Dynamic Graph Connectivity

RSS-Feed




Revision #1
Authors: Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
Accepted on: 8th June 2017 00:42
Downloads: 42
Keywords: 


Abstract:

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 word size, expected query time and worst case update time of a data structure for connectivity on graphs of size $n$. We provide simplified proofs of the following results:

-- Any data structure for connectivity with error at most $\frac{1}{32}$ must have $t_q \geq \Omega\left( \frac{\log n}{\log wt_u}\right) $. This was proved in the landmark paper of Fredman and Saks \cite{FredmanS89}.
-- For every $\delta>0$ and data structure for connectivity that makes no errors, if $t_u = o\left( \frac{\log n}{\log \log n}\right)$, then $t_q \geq \Omega\left( \delta n^{1-2\delta} \right)$. This was proved by Patrascu and Thorrup in \cite{PatrascuT11}.



Changes to previous version:

In the previous version of the paper, there was an error in the proof of Theorem 2. We retract that claim, and the current version presents simplified proofs of known results in literature.


Paper:

TR16-167 | 1st November 2016 18:07

New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity





TR16-167
Authors: Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao
Publication: 1st November 2016 20:42
Downloads: 348
Keywords: 


Abstract:

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