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.
- Ittai Abraham and Cyril Gavoille. 2011. On approximate distance labels and routing schemes with affine stretch. In DISC. 404--415. Google ScholarDigital Library
- 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 ScholarDigital Library
- Ittai Abraham and Ofer Neiman. 2012. Using petal-decompositions to build a low stretch spanning tree. In STOC. 395--406. Google ScholarDigital Library
- R. Agarwal. 2014a. Personal communication. (2014).Google Scholar
- 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 Scholar
- 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 ScholarDigital Library
- Rachit Agarwal, Philip Brighten Godfrey, and Sariel Har-Peled. 2011. Approximate distance queries and compact routing in sparse graphs. In INFOCOM. 1754--1762.Google Scholar
- Ingo Althöfer, Gautam Das, David P. Dobkin, and Deborah Joseph. 1990. Generating sparse spanners for weighted graphs. In SWAT. 26--37. Google ScholarDigital Library
- Yair Bartal. 1996. Probabilistic approximations of metric spaces and its algorithmic applications. In FOCS. 184--193. Google ScholarDigital Library
- 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 ScholarDigital Library
- Surender Baswana and Telikepalli Kavitha. 2006. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In FOCS. 591--602. Google ScholarDigital Library
- 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 ScholarDigital Library
- B. Bollobas. 1998. Extremal Graph Theory. Springer-Verlag. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- M. Elkin. 2001. Computing almost shortest paths. In Proceedings of the 20th ACM Symposium on Principles of Distributed Computing. 53--62. Google ScholarDigital Library
- Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. 2005. Lower-stretch spanning trees. In STOC. 494--503. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- S. Halperin and U. Zwick. 2000. Unpublished manuscript. (2000).Google Scholar
- 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 ScholarDigital Library
- A. Lubotsky, R. Phillips, and P. Sarnak. 1988. Ramanujan graphs. Combinatorica 8 (1988), 261--277.Google ScholarCross Ref
- J. Matousek. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Israeli J. Math. 93 (1996), 333--344.Google ScholarCross Ref
- Manor Mendel and Assaf Naor. 2006. Ramsey partitions and proximity data structures. In FOCS. 109--118. Google ScholarDigital Library
- Peter Bro Milterson. 1999. Cell probe complexity - A survey. In Invited Talk and Paper in Advances in Data Structures (Preconference Workshop of FSTTCS).Google Scholar
- Mihai Pǎtraşcu and Liam Roditty. 2010. Distance oracles beyond the Thorup-Zwick bound. In FOCS. 815--823. Google ScholarDigital Library
- Mihai Pǎtraşcu, Liam Roditty, and Mikkel Thorup. 2012. A new infinity of distance oracles for sparse graphs. In FOCS. 738--747. Google ScholarDigital Library
- 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 ScholarDigital Library
- D. Peleg and A. Schäffer. 1989. Graph spanners. Journal of Graph Theory 13 (1989), 99--116.Google ScholarCross Ref
- D. Peleg and E. Upfal. 1989. A tradeoff between size and efficiency for routing tables. Journal of the ACM 36 (1989), 510--530. Google ScholarDigital Library
- Seth Pettie. 2009. Low distortion spanners. ACM Transactions on Algorithms (TALG) 6, 1 (2009). Google ScholarDigital Library
- Ely Porat and Liam Roditty. 2013. Preprocess, set, query! Algorithmica 67, 4 (2013), 516--528.Google Scholar
- 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 Scholar
- Liam Roditty, Mikkel Thorup, and Uri Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In ICALP. 261--272. Google ScholarDigital Library
- Christian Sommer, Elad Verbin, and Wei Yu. 2009. Distance oracles for sparse graphs. In FOCS. 703--712. Google ScholarDigital Library
- M. Thorup and U. Zwick. 2001a. Approximate distance oracles. In Proceedings of the 33rd ACM Symposium on Theory of Computing. 183--192. Google ScholarDigital Library
- M. Thorup and U. Zwick. 2001b. Compact routing schemes. In Proceedings of the 13th Symposium on Parallelism in Algorithms and Architectures. 1--10. Google ScholarDigital Library
- M. Thorup and U. Zwick. 2006. Spanners and emulators with sublinear distance errors. In Proceedings of the Symposium on Discrete Algorithms. 802--809. Google ScholarDigital Library
- Christian Wulff-Nilsen. 2012. Approximate distance oracles with improved preprocessing time. In SODA. 202--208. Google ScholarDigital Library
Index Terms
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Recommendations
Approximate distance oracles with constant query time
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computingAn approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes of a given graph.
In this paper we consider approximate distance oracles for general undirected graphs with non-negative ...
A linear-size logarithmic stretch path-reporting distance oracle for general graphs
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithmsIn a seminal paper [27] for any n-vertex undirected graph G = (V, E) and a parameter k = 1, 2, . . ., Thorup and Zwick constructed a distance oracle of size O(kn1+1/k) which upon a query (u, v) constructs a path Π between u and v of length δ(u, v) such ...
Almost Optimal Exact Distance Oracles for Planar Graphs
We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q, and since the mid-1990s all results had polynomial time-...
Comments