skip to main content
research-article
Public Access

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

Published:03 August 2016Publication History
Skip Abstract Section

Abstract

Thorup and Zwick [2001a] proposed a landmark distance oracle with the following properties. Given an n-vertex undirected graph G = (V, E) and a parameter k = 1, 2, …, their oracle has size O(kn1 + 1/k), and upon a query (u, v) it constructs a path Π between u and v of length δ(u, v) such that dG(u, v) ⩽ δ(u, v) ⩽ (2k − 1)dG(u, v). The query time of the oracle from Thorup and Zwick [2001a] is O(k) (in addition to the length of the returned path), and it was subsequently improved to O(1) [Wulff-Nilsen 2012; Chechik 2014]. A major drawback of the oracle of Thorup and Zwick [2001a] is that its space is Ω(n · logn). Mendel and Naor [2006] devised an oracle with space O(n1 + 1/k) and stretch O(k), but their oracle can only report distance estimates and not actual paths. In this article, we devise a path-reporting distance oracle with size O(n1 + 1/k), stretch O(k), and query time O(nϵ), for an arbitrarily small constant ϵ > 0. In particular, for k = logn, our oracle provides logarithmic stretch using linear size. Another variant of our oracle has size O(nloglogn), polylogarithmic stretch, and query time O(loglogn).

For unweighted graphs, we devise a distance oracle with multiplicative stretch O(1), additive stretch O(β(k)), for a function β(·), space O(n1 + 1/k), and query time O(nϵ), for an arbitrarily small constant ϵ > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erdős’s girth conjecture threshold (which is stretch 2k − 1 and size O(n1 + 1/k)). Breaking the girth conjecture tradeoff is achieved by exhibiting a tradeoff of different nature between additive stretch β(k) and size O(n1 + 1/k). A similar type of tradeoff was exhibited by a construction of (1 + ϵ, β)-spanners due to Elkin and Peleg [2001]. However, so far (1 + ϵ, β)-spanners had no counterpart in the distance oracles’ world.

An important novel tool that we develop on the way to these results is a distance-preserving path-reporting oracle. We believe that this oracle is of independent interest.

References

  1. Ittai Abraham and Cyril Gavoille. 2011. On approximate distance labels and routing schemes with affine stretch. In DISC. 404--415. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. 2006. On space-stretch trade-offs: Lower bounds. In Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures. 207--216. DOI:http://dx.doi.org/10.1145/1148109.1148143 Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Ittai Abraham and Ofer Neiman. 2012. Using petal-decompositions to build a low stretch spanning tree. In STOC. 395--406. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. R. Agarwal. 2014a. Personal communication. (2014).Google ScholarGoogle Scholar
  5. Rachit Agarwal. 2014b. The space-stretch-time tradeoff in distance oracles. In Algorithms - ESA 2014 (Lecture Notes in Computer Science), Andreas S. Schulz and Dorothea Wagner (Eds.), Vol. 8737. Springer Berlin, 49--60. DOI:http://dx.doi.org/10.1007/978-3-662-44777-2_5Google ScholarGoogle Scholar
  6. Rachit Agarwal and Philip Brighten Godfrey. 2013. Distance oracles for stretch less than 2. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13). 526--538. DOI:http://dx.doi.org/10.1137/1.9781611973105.38 Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Rachit Agarwal, Philip Brighten Godfrey, and Sariel Har-Peled. 2011. Approximate distance queries and compact routing in sparse graphs. In INFOCOM. 1754--1762.Google ScholarGoogle Scholar
  8. Ingo Althöfer, Gautam Das, David P. Dobkin, and Deborah Joseph. 1990. Generating sparse spanners for weighted graphs. In SWAT. 26--37. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Yair Bartal. 1996. Probabilistic approximations of metric spaces and its algorithmic applications. In FOCS. 184--193. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Surender Baswana, Akshay Gaur, Sandeep Sen, and Jayant Upadhyay. 2008. Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In ICALP (1). 609--621. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Surender Baswana and Telikepalli Kavitha. 2006. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In FOCS. 591--602. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Surender Baswana and Sandeep Sen. 2006. Approximate distance oracles for unweighted graphs in expected O(n2) time. ACM Transactions on Algorithms (TALG) 2, 4 (2006), 557--577. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. B. Bollobas. 1998. Extremal Graph Theory. Springer-Verlag. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Shiri Chechik. 2014. Approximate distance oracles with constant query time. In Proceedings of the Symposium on Theory of Computing (STOC'14). 654--663. DOI:http://dx.doi.org/10.1145/2591796.2591801 Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. D. Coppersmith and M. Elkin. 2005. Sparse source-wise and pair-wise distance preservers. In SODA: ACM-SIAM Symposium on Discrete Algorithms. 660--669. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. M. Elkin. 2001. Computing almost shortest paths. In Proceedings of the 20th ACM Symposium on Principles of Distributed Computing. 53--62. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. 2005. Lower-stretch spanning trees. In STOC. 494--503. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Michael Elkin, Ofer Neiman, and Christian Wulff-Nilsen. 2014. Space-efficient path-reporting distance oracles. CoRR abs/1410.0768 (2014). http://arxiv.org/abs/1410.0768.Google ScholarGoogle Scholar
  19. M. Elkin and D. Peleg. 2001. Spanner constructions for general graphs. In Proceedings of the 33th ACM Symposium on Theory of Computing. 173--182. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Michael Elkin and Seth Pettie. 2015. A linear-size logarithmic stretch path-reporting distance oracle for general graphs. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 805--821. DOI:http://dx.doi.org/10.1137/1.9781611973730.55 Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. S. Halperin and U. Zwick. 2000. Unpublished manuscript. (2000).Google ScholarGoogle Scholar
  22. F. Lazebnik and V. A. Ustimenko. 1995. Explicit construction of graphs with an arbitrary large girth and of large size. Discrete Applied Mathematics 60, 1--3 (1995), 275--284. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. A. Lubotsky, R. Phillips, and P. Sarnak. 1988. Ramanujan graphs. Combinatorica 8 (1988), 261--277.Google ScholarGoogle ScholarCross RefCross Ref
  24. J. Matousek. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Israeli J. Math. 93 (1996), 333--344.Google ScholarGoogle ScholarCross RefCross Ref
  25. Manor Mendel and Assaf Naor. 2006. Ramsey partitions and proximity data structures. In FOCS. 109--118. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Peter Bro Milterson. 1999. Cell probe complexity - A survey. In Invited Talk and Paper in Advances in Data Structures (Preconference Workshop of FSTTCS).Google ScholarGoogle Scholar
  27. Mihai Pǎtraşcu and Liam Roditty. 2010. Distance oracles beyond the Thorup-Zwick bound. In FOCS. 815--823. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Mihai Pǎtraşcu, Liam Roditty, and Mikkel Thorup. 2012. A new infinity of distance oracles for sparse graphs. In FOCS. 738--747. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. David Peleg. 2000. Proximity-preserving labeling schemes. Journal of Graph Theory 33, 3 (2000), 167--176. DOI:http://dx.doi.org/10.1002/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5 Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. D. Peleg and A. Schäffer. 1989. Graph spanners. Journal of Graph Theory 13 (1989), 99--116.Google ScholarGoogle ScholarCross RefCross Ref
  31. D. Peleg and E. Upfal. 1989. A tradeoff between size and efficiency for routing tables. Journal of the ACM 36 (1989), 510--530. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. Seth Pettie. 2009. Low distortion spanners. ACM Transactions on Algorithms (TALG) 6, 1 (2009). Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. Ely Porat and Liam Roditty. 2013. Preprocess, set, query! Algorithmica 67, 4 (2013), 516--528.Google ScholarGoogle Scholar
  34. Liam Roditty. 2015. Distance oracles for sparse graphs. In Encyclopedia of Algorithms. DOI:http://dx.doi.org/10.1007/978-3-642-27848-8_571-1Google ScholarGoogle Scholar
  35. Liam Roditty, Mikkel Thorup, and Uri Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In ICALP. 261--272. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. Christian Sommer, Elad Verbin, and Wei Yu. 2009. Distance oracles for sparse graphs. In FOCS. 703--712. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. M. Thorup and U. Zwick. 2001a. Approximate distance oracles. In Proceedings of the 33rd ACM Symposium on Theory of Computing. 183--192. Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. M. Thorup and U. Zwick. 2001b. Compact routing schemes. In Proceedings of the 13th Symposium on Parallelism in Algorithms and Architectures. 1--10. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. M. Thorup and U. Zwick. 2006. Spanners and emulators with sublinear distance errors. In Proceedings of the Symposium on Discrete Algorithms. 802--809. Google ScholarGoogle ScholarDigital LibraryDigital Library
  40. Christian Wulff-Nilsen. 2012. Approximate distance oracles with improved preprocessing time. In SODA. 202--208. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in

        Full Access

        • Published in

          cover image ACM Transactions on Algorithms
          ACM Transactions on Algorithms  Volume 12, Issue 4
          September 2016
          310 pages
          ISSN:1549-6325
          EISSN:1549-6333
          DOI:10.1145/2983296
          Issue’s Table of Contents

          Copyright © 2016 ACM

          Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 3 August 2016
          • Revised: 1 January 2016
          • Accepted: 1 January 2016
          • Received: 1 July 2015
          Published in talg Volume 12, Issue 4

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • research-article
          • Research
          • Refereed

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader