Algorithmic and hardness results for the hub labeling problem

DOI10.1137/1.9781611974782.94MaRDI QIDQ4575837zbMATH OpenOpenAlexFDO

Authors Haris Angelidakis, Yury Makarychev, Vsevolod Oparin

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06605

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the hub labeling framework. In this paper, we study the approximability of the Hub Labeling problem. We prove a hardness of $Omega(logn)$ for Hub Labeling, matching known approximation guarantees. The hardness result applies to graphs that have multiple shortest paths between some pairs of vertices. No hardness of approximation results were known previously. Then, we focus on graphs that have a unique shortest path between each pair of vertices. This is a very natural family of graphs, and much research on the Hub Labeling problem has studied such graphs. We give an $O(logD)$ approximation algorithm for graphs of diameter $D$ with unique shortest paths. In particular, we get an $O(loglogn)$ approximation for graphs of polylogarithmic diameter, while previously known algorithms gave an $O(logn)$ proximation. Finally, we present a polynomial-time approximation scheme (PTAS) and quasi-polynomial time algorithms for Hub Labeling on trees; additionally, we analyze a simple combinatorial heuristic for Hub Labeling on trees, proposed by Peleg in 2000. We show that this heuristic gives an approximation factor of 2.

Recommendations

• On the complexity of hub labeling (extended abstract)
• Algorithms for hub label optimization
• Algorithms for hub label optimization
• Hierarchical hub labelings for shortest paths
• Separating Hierarchical and General Hub Labelings

Cited in

(13)

• Eccentricity queries and beyond using hub labels
• The hierarchical hub labeling is non-efficient
• On the complexity of hub labeling (extended abstract)
• Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
• Algorithms for hub label optimization
• Exploiting hopsets: improved distance oracles for graphs of constant highway dimension and beyond
• Hardness of exact distance queries in sparse graphs through hub labeling
• Algorithms for hub label optimization
• Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
• Exact and approximate hierarchical hub labeling
• The complexity of landmark hub labeling
• Parameterized upper bounds for path-consistent hub labeling
• Insights into (k,)-shortcutting algorithms

This page was built for publication: Algorithmic and hardness results for the hub labeling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575837)