ECCC-Report TR16-167https://eccc.weizmann.ac.il/report/2016/167Comments and Revisions published for TR16-167en-usThu, 08 Jun 2017 00:42:13 +0300
Revision 1
| Simplified Data Structure Lower Bounds for Dynamic Graph Connectivity |
Sivaramakrishnan Natarajan Ramamoorthy,
Anup Rao
https://eccc.weizmann.ac.il/report/2016/167#revision1The 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}.Thu, 08 Jun 2017 00:42:13 +0300https://eccc.weizmann.ac.il/report/2016/167#revision1
Paper TR16-167
| New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity |
Sivaramakrishnan Natarajan Ramamoorthy,
Anup Rao
https://eccc.weizmann.ac.il/report/2016/167The 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) $. Tue, 01 Nov 2016 20:42:07 +0200https://eccc.weizmann.ac.il/report/2016/167