Gupta, Siddharth ;
Kosowski, Adrian ;
Viennot, Laurent
Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond
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 hhop 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 hhopset and may be applied in processing distance queries on graph G. In particular, a 2hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on 3hopsets 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 3hopsets 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 2hopsets. Finally, we consider the problem of computing minimumsize hhopset (for any h >= 2) for a given graph G, showing a polylogarithmicfactor 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 3hopset oracle given the space bound.
BibTeX  Entry
@InProceedings{gupta_et_al:LIPIcs:2019:10719,
author = {Siddharth Gupta and Adrian Kosowski and Laurent Viennot},
title = {{Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {143:1143:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10719},
URN = {urn:nbn:de:0030drops107199},
doi = {10.4230/LIPIcs.ICALP.2019.143},
annote = {Keywords: Hopsets, Distance Oracles, Graph Algorithms, Data Structures}
}
04.07.2019
Keywords: 

Hopsets, Distance Oracles, Graph Algorithms, Data Structures 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 