Parameterized Upper Bounds for Path-Consistent Hub Labeling

Hub labeling (HL) comprises a class of algorithms that construct fast distance oracles on weighted graphs. The goal of HL is to assign each node a label such that the shortest path distance between any node pair can be deduced solely based on their label information. HL has been extensively studied from a theoretical and practical perspective, including parameterized upper bounds. It was shown that average label sizes in \(\mathcal {O}(\kappa \log n)\) are possible where \(\kappa \) denotes the skeleton dimension of the graph. In this paper, we focus on a special type of HL, called path-consistent HL (PC-HL). This type of labeling is beneficial for fast shortest path extraction and compact storage. We prove novel parameterized upper bounds for path-consistent labelings (which also apply to HL). In particular, we show that label sizes can be bounded by \(\mathcal {O}(gt \log n)\) where gt denotes the geodesic transversal number. Furthermore, we propose a new variant \(\kappa ^+\) of the skeleton dimension, show that there are graphs where \(\kappa ^+\) is a factor of \(\varTheta (\sqrt{n})\) smaller than \(\kappa \) , and prove that \(\mathcal {O}(\kappa ^{(+)} \log n)\) constitutes a valid upper bound for the label size of a PC-HL. We devise polytime algorithms to construct labelings that adhere to the parameterized upper bounds. Those are the first non-hierarchical labelings that are path-consistent, which were not known to exist before. Furthermore, we prove that gt and \(\kappa ^{(+)}\) are incomparable. We also compute their values on diverse benchmark graphs to assess which of them provides tighter upper bounds in practice.