Exact Distance Oracles Using Hopsets

Siddharth Gupta 1 Adrian Kosowski 2 Laurent Viennot 2
2 GANG - Networks, Graphs and Algorithms
Inria de Paris, IRIF - Institut de Recherche en Informatique Fondamentale
Abstract : For fixed $h \geq 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 while incurring only a quadratic increase in the query decoding time, and actually offer a speedup 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 \geq 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 hopsets achieving polylog approximation both for space and query time compared to the optimal $3$-hopset oracle given the space bound.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download

https://hal.inria.fr/hal-01737210
Contributor : Adrian Kosowski <>
Submitted on : Monday, March 19, 2018 - 12:44:31 PM
Last modification on : Sunday, May 26, 2019 - 1:13:05 AM
Long-term archiving on : Tuesday, September 11, 2018 - 8:02:01 AM

Files

Identifiers

  • HAL Id : hal-01737210, version 1
  • ARXIV : 1803.06977

Citation

Siddharth Gupta, Adrian Kosowski, Laurent Viennot. Exact Distance Oracles Using Hopsets. 2018. ⟨hal-01737210v1⟩

Share

Metrics

Record views

154

Files downloads

79