Skip to main navigation Skip to search Skip to main content

Tight lower bounds for st-connectivity on the nnjag model

  • Jeff Edmonds
  • , Chung Keung Poon
  • , Dimitris Achlioptas

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Abstract

Directed st-connectivity is the problem of deciding whether or not there exists a path from a distinguished node s to a distinguished node t in a directed graph. We prove a timespace lower bound on the probabilistic NNJAG model of Poon [Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 218-227]. Let n be the number of nodes in the input graph and S and T be the space and time used by the NNJAG, respectively. We show that, for any δ > 0, if an NNJAG uses space S ∈ O(n1-δ), then T ∈ 2Ω(log2(n/S)); otherwise T ∈ 2Ωlog22(n log n/S)/log log n) × (nS/log n)1/2 preliminary version of this paper by Edmonds and Poon [Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147-156.], a lower bound of T ∈ 2Ωlog22(n log n/S)/log log n) × (nS/logn)1/2 was proved.) Our result greatly improves the previous lower bound of ST ∈ Ω(n2/logn) on the JAG model by Barnes and Edmonds [Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228-237] and that of S1/3T ∈ Ω(n4/3) on the NNJAG model by Edmonds [Time-Space Lower Bounds for Undirected and Directed S T-Connectivity on JAG Models, Ph.D. thesis, University of Toronto, Toronto, ON, Canada, 1993]. Our lower bound is tight for S ∈ O(n1-δ), for any δ > 0, matching the upper bound of Barnes et al.[Proc. 7th Annual IEEE Conference on Structure in Complexity Theory, Boston, MA, 1992, pp. 27-331. As a corollary of this improved lower bound, we obtain the first tight space lower bound of Ω(log2 n) on the NNJAG model. No tight space lower bound was previously known even for the more restricted JAG model. © 1999 Society for Industrial and Applied Mathematics.
Original languageEnglish
Pages (from-to)2257-2284
JournalSIAM Journal on Computing
Volume28
Issue number6
DOIs
Publication statusPublished - 1999

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Research Keywords

  • Connectivity
  • Lower bounds
  • Space complexity
  • Space-time tradeoffs

Fingerprint

Dive into the research topics of 'Tight lower bounds for st-connectivity on the nnjag model'. Together they form a unique fingerprint.

Cite this