Document Open Access Logo

Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond

Authors Siddharth Gupta, Adrian Kosowski, Laurent Viennot

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.143.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Siddharth Gupta
  • Ben-Gurion University of the Negev, Israel
Adrian Kosowski
  • Inria, Paris, France
Laurent Viennot
  • Inria, Paris, France

Funding

  • Gupta, Siddharth: Supported in part by the Zuckerman STEM Leadership Program.
  • Kosowski, Adrian: Supported by ANR project DESCARTES (ANR-16-CE40-0023).
  • Viennot, Laurent: Supported by ANR project DISTANCIA (ANR-17-CE40-0015) and ANR project MULTIMOD (ANR-17-CE22-0016).

Cite As Get BibTex

Siddharth Gupta, Adrian Kosowski, and Laurent Viennot. Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 143:1-143:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.143

Abstract

For fixed h >= 2, we consider the task of adding to a graph G a set of weighted shortcut edges on the same vertex set, such that the length of a shortest h-hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in G. A set of shortcut edges with this property is called an exact h-hopset and may be applied in processing distance queries on graph G. In particular, a 2-hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on 3-hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that 3-hopsets require exponentially fewer shortcuts per node than any previously described distance oracle, and also offer a speedup in query time when compared to simple oracles based on a direct application of 2-hopsets. Finally, we consider the problem of computing minimum-size h-hopset (for any h >= 2) for a given graph G, showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When h=3, for a given bound on the space used by the distance oracle, we provide a construction of hopset achieving polylog approximation both for space and query time compared to the optimal 3-hopset oracle given the space bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Data structures design and analysis
Keywords
  • Hopsets
  • Distance Oracles
  • Graph Algorithms
  • Data Structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Greg Bodwin, and Seth Pettie. A Hierarchy of Lower Bounds for Sublinear Additive Spanners. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 568-576. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.36.
  2. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. VC-dimension and shortest path algorithms. In ICALP, volume 6755 of Lecture Notes in Computer Science, pages 690-699. Springer, 2011. Google Scholar
  3. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway Dimension and Provably Efficient Shortest Path Algorithms. J. ACM, 63(5):41:1-41:26, 2016. URL: http://dx.doi.org/10.1145/2985473.
  4. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway Dimension and Provably Efficient Shortest Path Algorithms. J. ACM, 63(5):41:1-41:26, 2016. URL: http://dx.doi.org/10.1145/2985473.
  5. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 782-793. SIAM, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.64.
  6. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In Chin-Wan Chung, Andrei Z. Broder, Kyuseok Shim, and Torsten Suel, editors, 23rd International World Wide Web Conference, WWW '14, Seoul, Republic of Korea, April 7-11, 2014, pages 237-248. ACM, 2014. URL: http://dx.doi.org/10.1145/2566486.2568007.
  7. Noga Alon and Baruch Schieber. Optimal preprocessing for answering on-line product queries. Technical Report 71/87, Tel Aviv University, 1987. Google Scholar
  8. Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear Distance Labeling. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 5:1-5:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.5.
  9. Haris Angelidakis, Yury Makarychev, and Vsevolod Oparin. Algorithmic and Hardness Results for the Hub Labeling Problem. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1442-1461. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.94.
  10. Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, and Christos D. Zaroliagis. Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane. In Josep Díaz and Maria J. Serna, editors, Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996, Proceedings, volume 1136 of Lecture Notes in Computer Science, pages 514-528. Springer, 1996. URL: http://dx.doi.org/10.1007/3-540-61680-2_79.
  11. H. Bast, Stefan Funke, and Domagoj Matijevic. Ultrafast Shortest-Path Queries via Transit Nodes. In Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors, The Shortest Path Problem, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 13-14, 2006, volume 74 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 175-192. DIMACS/AMS, 2006. Google Scholar
  12. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-Closure Spanners. SIAM J. Comput., 41(6):1380-1425, 2012. URL: http://dx.doi.org/10.1137/110826655.
  13. Hans L. Bodlaender, Gerard Tel, and Nicola Santoro. Trade-Offs in Non-Reversing Diameter. Nord. J. Comput., 1(1):111-134, 1994. Google Scholar
  14. Sergio Cabello. Many Distances in Planar Graphs. Algorithmica, 62(1-2):361-381, 2012. URL: http://dx.doi.org/10.1007/s00453-010-9459-0.
  15. Shiva Chaudhuri and Christos D. Zaroliagis. Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmica, 27(3):212-226, 2000. URL: http://dx.doi.org/10.1007/s004530010016.
  16. Bernard Chazelle. Computing on a Free Tree via Complexity-Preserving Mappings. Algorithmica, 2:337-361, 1987. URL: http://dx.doi.org/10.1007/BF01840366.
  17. Danny Z. Chen and Jinhui Xu. Shortest path queries in planar graphs. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 469-478, 2000. URL: http://dx.doi.org/10.1145/335305.335359.
  18. Edith Cohen. Using Selective Path-Doubling for Parallel Shortest-Path Computations. J. Algorithms, 22(1):30-56, 1997. URL: http://dx.doi.org/10.1006/jagm.1996.0813.
  19. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM, 47(1):132-166, 2000. URL: http://dx.doi.org/10.1145/331605.331610.
  20. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and Distance Queries via 2-Hop Labels. SIAM J. Comput., 32(5):1338-1355, May 2003. URL: http://dx.doi.org/10.1137/S0097539702403098.
  21. Vincent Cohen-Addad, Søren Dahlgaard, and Christian Wulff-Nilsen. Fast and Compact Exact Distance Oracle for Planar Graphs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 962-973, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.93.
  22. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Robust Distance Queries on Massive Networks. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 321-333. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_27.
  23. Hristo Djidjev. On-Line Algorithms for Shortest Path Problems on Planar Digraphs. In Fabrizio d'Amore, Paolo Giulio Franciosa, and Alberto Marchetti-Spaccamela, editors, Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG '96, Cadenabbia (Como), Italy, June 12-14, 1996, Proceedings, volume 1197 of Lecture Notes in Computer Science, pages 151-165. Springer, 1996. URL: http://dx.doi.org/10.1007/3-540-62559-3_14.
  24. Michael Elkin and Ofer Neiman. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 128-137. IEEE Computer Society, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.22.
  25. Michael Elkin and Ofer Neiman. Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR, abs/1704.08468, 2017. URL: http://arxiv.org/abs/1704.08468.
  26. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868-889, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.05.007.
  27. Arash Farzan and Shahin Kamali. Compact Navigation and Distance Oracles for Graphs with Small Treewidth. Algorithmica, 69(1):92-116, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9712-9.
  28. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance Labeling in Graphs. J. Algorithms, 53(1):85-112, October 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2004.05.002.
  29. Pawel Gawrychowski, Adrian Kosowski, and Przemyslaw Uznanski. Sublinear-Space Distance Labeling Using Hubs. In Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, pages 230-242, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_17.
  30. Pawel Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen. Better Tradeoffs for Exact Distance Oracles in Planar Graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 515-529, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.34.
  31. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. In Catherine C. McGeoch, editor, Experimental Algorithms, 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30-June 1, 2008, Proceedings, volume 5038 of Lecture Notes in Computer Science, pages 319-333. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-68552-4_24.
  32. Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck. Reach for A*: Efficient Point-to-Point Shortest Path Algorithms. In ALENEX, pages 129-143. SIAM, 2006. Google Scholar
  33. Siddharth Gupta, Adrian Kosowski, and Laurent Viennot. Exact Distance Oracles Using Hopsets. CoRR, abs/1803.06977, 2018. URL: http://arxiv.org/abs/1803.06977.
  34. Ronald J. Gutman. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In ALENEX/ANALCO, pages 100-111. SIAM, 2004. Google Scholar
  35. Philip N. Klein and Sairam Subramanian. A Randomized Parallel Algorithm for Single-Source Shortest Paths. J. Algorithms, 25(2):205-220, 1997. URL: http://dx.doi.org/10.1006/jagm.1997.0888.
  36. Adrian Kosowski and Laurent Viennot. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. CoRR, abs/1609.00512, 2016. URL: http://arxiv.org/abs/1609.00512.
  37. Adrian Kosowski and Laurent Viennot. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1462-1478. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.95.
  38. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
  39. Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. URL: http://dx.doi.org/10.1007/BF02579324.
  40. Hanmao Shi and Thomas H. Spencer. Time-Work Tradeoffs of the Single-Source Shortest Paths Problem. J. Algorithms, 30(1):19-32, 1999. URL: http://dx.doi.org/10.1006/jagm.1998.0968.
  41. Mikkel Thorup. Shortcutting Planar Digraphs. Combinatorics, Probability & Computing, 4:287-315, 1995. URL: http://dx.doi.org/10.1017/S0963548300001668.
  42. Mikkel Thorup. Parallel Shortcutting of Rooted Trees. J. Algorithms, 23(1):139-159, 1997. URL: http://dx.doi.org/10.1006/jagm.1996.0829.
  43. Jeffrey D. Ullman and Mihalis Yannakakis. High-Probability Parallel Transitive Closure Algorithms. In SPAA, pages 200-209, 1990. URL: http://dx.doi.org/10.1145/97444.97686.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact