It was first formally defined by Abraham et al.[1] based on the observation by Bast et al.[2][3] that any road network has a sparse set of "transit nodes", such that driving from a point A to a sufficiently far away point B along the shortest route will always pass through one of these transit nodes.
It has also been proposed that the highway dimension captures the properties of public transportation networks well (at least according to definitions 1 and 2 below), given that longer routes using busses, trains, or airplanes will typically be serviced by larger transit hubs (stations and airports).
This relates to the spoke–hub distribution paradigm in transport topology optimization.
To measure the highway dimension we determine the "sparseness" of a hitting set of a subset of
in a local area of the graph, for which we define a ball of radius
In the context of low highway dimension graphs, the vertices of a hitting set for the shortest paths are called hubs.
The original definition[1] of the highway dimension measures the sparseness of a hub set
Choosing a constant greater than 4 implies additional structural properties of graphs of bounded highway dimension, which can be exploited algorithmically.
A subsequent definition[6] of the highway dimension measures the sparseness of a hub set
For the third definition[7] of the highway dimension we introduce the notion of a "witness path": for a given radius
A notion closely related to the highway dimension is that of a shortest path cover,[1] where the order of the quantifiers in the definition is reversed, i.e., instead of a hub set for each ball, there is a one hub set
[4] For algorithmic purposes it is often more convenient to work with one hitting set for each radius
, which makes shortest path covers an important tool for algorithms on graphs of bounded highway dimension.
In particular, for any graph it is possible to choose edge lengths such that the highway dimension is
,[5] while at the same time some graphs with very simple structure such as trees can have arbitrarily large highway dimension.
On the other hand, a star with unit edge lengths has highway dimension
[5] Assuming that all shortest paths are unique (which can be done by slightly perturbing the edge lengths), an
-approximation can be computed in polynomial time,[6] given that the highway dimension of the graph is
It is not known whether computing the highway dimension is fixed-parameter tractable (FPT), however there are hardness results indicating that this is likely not the case.
[8] In particular, these results imply that, under standard complexity assumptions, an FPT algorithm can neither compute the highway dimension bottom-up (from the smallest value
Some heuristics to compute shortest paths, such as the Reach, Contraction Hierarchies, Transit Nodes, and Hub Labelling algorithms, can be formally proven to run faster than other shortest path algorithms (e.g. Dijkstra's algorithm) on graphs of bounded highway dimension according to definition 3 above.
A crucial property that can be exploited algorithmically for graphs of bounded highway dimension is that vertices that are far from the hubs of a shortest path cover are clustered into so-called towns:[5]Given a radius
For a graph of bounded highway dimension (according to definition 1 above) this decomposition can be used to find a metric embedding into a graph of bounded treewidth that preserves distances between vertices arbitrarily well.
Due to this embedding it is possible to obtain quasi-polynomial time approximation schemes (QPTASs) for various problems such as Travelling Salesman (TSP), Steiner Tree, k-Median, and Facility Location.
[5] For clustering problems such as k-Median, k-Means, and Facility Location, faster polynomial-time approximation schemes (PTASs) are known for graphs of bounded highway dimension according to definition 1 above.
[9] For network design problems such as TSP and Steiner Tree it is not known how to obtain a PTAS.
For the k-Center problem, it is not known whether a PTAS exists for graphs of bounded highway dimension, however it is NP-hard to compute a (
)-approximation algorithm needs at least double exponential time in the highway dimension, unless P=NP.
[10] When using definition 1 above, a parameterized approximation scheme (PAS) is known to exist when using
[12] This is notable, since typically (i.e., for all the problems mentioned above), if there is an approximation scheme for metrics of low doubling dimension, then there is also one for graphs of bounded highway dimension.