License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.20
URN: urn:nbn:de:0030-drops-128861
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12886/
Go to the corresponding LIPIcs Volume Portal

Blum, Johannes ; Storandt, Sabine

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

pdf-format:
LIPIcs-ESA-2020-20.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{blum_et_al:LIPIcs:2020:12886,
  author =	{Johannes Blum and Sabine Storandt},
  title =	{{Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12886},
  URN =		{urn:nbn:de:0030-drops-128861},
  doi =		{10.4230/LIPIcs.ESA.2020.20},
  annote =	{Keywords: contraction hierarchies, search space size, balanced separator, tree decomposition}
}

Keywords: contraction hierarchies, search space size, balanced separator, tree decomposition
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI