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