On the Complexity of Hub Labeling (Extended Abstract)
Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type ofHL, that received a lot of attention from a practical point of view. However, theoretical questions such as NP-hardness and approximation guarantees for HHL algorithms have been left aside. We study the computational complexity of HL and HHL. We prove that both HL and HHL are NP-hard, and present upper and lower bounds on the approximation ratios of greedy HHL algorithms that are used in practice. We also introduce a new variant of the greedy HHL algorithm that produces small labels for graphs with small highway dimension.