Document Open Access Logo

Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies

Authors Johannes Blum , Sabine Storandt

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.20.pdf
  • Filesize: 434 kB
  • 14 pages

Document Identifiers

Author Details

Johannes Blum
  • University of Konstanz, Germany
Sabine Storandt
  • University of Konstanz, Germany

Cite As Get BibTex

Johannes Blum and Sabine Storandt. Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.20

Abstract

Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing the search space size of a bidirectional Dijkstra run. To explain the practical success of CH, several theoretical upper bounds for the maximum search space size were derived in previous work. For example, it was shown that in minor-closed graph families search space sizes in 𝒪(√n) can be achieved (with n denoting the number of nodes in the graph), and search space sizes in 𝒪(h log D) in graphs of highway dimension h and diameter D. In this paper, we primarily focus on lower bounds. We prove that the average search space size in a so called weak CH is in Ω(b_α) for α ≥ 2/3 where b_α is the size of a smallest α-balanced node separator. This discovery allows us to describe the first approximation algorithm for the average search space size. Our new lower bound also shows that the 𝒪(√n) bound for minor-closed graph families is tight. Furthermore, we deeper investigate the relationship of CH and the highway dimension and skeleton dimension of the graph, and prove new lower bound and incomparability results. Finally, we discuss how lower bounds for strong CH can be obtained from solving a HittingSet problem defined on a set of carefully chosen subgraphs of the input network.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • contraction hierarchies
  • search space size
  • balanced separator
  • tree decomposition

Metrics

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

References

  1. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway dimension and provably efficient shortest path algorithms. Technical Report MSR-TR-2013-91, Microsoft Research, September 2013. Google Scholar
  2. Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato Fonseca F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 782-793, 2010. Google Scholar
  3. Ajit Agrawal, Philip Klein, and R Ravi. Cutting down on fill using nested dissection: provably good elimination orderings. In Graph Theory and Sparse Matrix Computation, pages 31-55. Springer, 1993. Google Scholar
  4. Eyal Amir, Robert Krauthgamer, and Satish Rao. Constant factor approximation of vertex-cuts in planar graphs. In ACM Symposium on Theory of Computing (STOC), pages 90-99, 2003. Google Scholar
  5. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. Route planning in transportation networks. In Algorithm engineering, pages 19-80. Springer, 2016. Google Scholar
  6. Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner. Preprocessing speed-up techniques is hard. In International Conference on Algorithms and Complexity (CIAC), pages 359-370. Springer, 2010. Google Scholar
  7. Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space size in contraction hierarchies. Theoretical Computer Science, 645:112-127, 2016. Google Scholar
  8. Johannes Blum, Stefan Funke, and Sabine Storandt. Sublinear search spaces for shortest path planning in grid and road networks. In AAAI Conference on Artificial Intelligence, 2018. Google Scholar
  9. Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms, 18(2):238-255, 1995. URL: https://doi.org/10.1006/jagm.1995.1009.
  10. Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5):1338-1355, 2003. Google Scholar
  11. Tobias Columbus. Search space size in contraction hierarchies. Diploma thesis, Karlsruhe Institute of Technology, 2012. Google Scholar
  12. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. In International Symposium on Experimental Algorithms (SEA), pages 271-282, 2014. Google Scholar
  13. Hristo Nicolov Djidjev. On the problem of partitioning planar graphs. SIAM Journal on Algebraic Discrete Methods, 3(2):229-240, 1982. Google Scholar
  14. Stefan Funke and Sabine Storandt. Provable efficiency of contraction hierarchies with randomized preprocessing. In International Symposium on Algorithms and Computation (ISAAC), pages 479-490, 2015. Google Scholar
  15. Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388-404, 2012. URL: https://doi.org/10.1287/trsc.1110.0401.
  16. Thor Johnson, Neil Robertson, Paul D Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138-154, 2001. Google Scholar
  17. Adrian Kosowski and Laurent Viennot. Beyond highway dimension: Small distance labels using tree skeletons. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1462-1478, 2017. Google Scholar
  18. Tom Leighton and Satish Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. Technical report, MASSACHUSETTS INST OF TECH CAMBRIDGE MICROSYSTEMS RESEARCH CENTER, 1989. Google Scholar
  19. Nikola Milosavljević. On optimal preprocessing for contraction hierarchies. In ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS), pages 33-38. ACM, 2012. Google Scholar
  20. Tobias Rupp and Stefan Funke. A lower bound for the query phase of contraction hierarchies and hub labels. In Computer Science in Russia (CSR), 2020. Google Scholar
  21. Alejandro A Schäffer. Optimal node ranking of trees in linear time. Information Processing Letters, 33(2):91-96, 1989. Google Scholar
  22. Colin White. Lower bounds in the preprocessing and query phases of routing algorithms. In Annual European Symposium on Algorithms (ESA), pages 1013-1024, 2015. Google Scholar
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