Highway dimension

The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. 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.

Definitions

Several definitions of the highway dimension exist.^[4] Each definition of the highway dimension uses a hitting set of a certain set of shortest paths: given a graph ${\displaystyle G=(V,E)}$ with edge lengths ${\displaystyle \ell :E\to \mathbb {R} ^{+}}$, let ${\displaystyle {\mathcal {P}}}$ contain every vertex set ${\displaystyle P\subseteq V}$ such that ${\displaystyle P}$ induces a shortest path between some vertex pair of ${\displaystyle G}$, according to the edge lengths ${\displaystyle \ell }$. To measure the highway dimension we determine the "sparseness" of a hitting set of a subset of ${\displaystyle {\mathcal {P}}}$ in a local area of the graph, for which we define a ball of radius ${\displaystyle r>0}$ around a vertex ${\displaystyle u\in V}$ to be the set ${\displaystyle B_{r}(u)\subseteq V}$ of vertices at distance at most ${\displaystyle r}$ from ${\displaystyle u}$ in ${\displaystyle G}$ according to the edge lengths ${\displaystyle \ell }$. In the context of low highway dimension graphs, the vertices of a hitting set for the shortest paths are called hubs.

Definition 1

The original definition^[1] of the highway dimension measures the sparseness of a hub set ${\displaystyle H}$ of shortest paths contained within a ball of radius ${\displaystyle 4r}$:

The highway dimension of ${\displaystyle G}$ is the smallest integer ${\displaystyle h_{1}}$ such that for any radius ${\displaystyle r>0}$ and any node ${\displaystyle u\in V}$ there is a hitting set ${\displaystyle H\subseteq B_{4r}(u)}$ of size at most ${\displaystyle h_{1}}$ for all shortest paths ${\displaystyle P\in {\mathcal {P}}}$ of length more than ${\displaystyle r}$ for which ${\displaystyle P\subseteq B_{4r}(u)}$.

A variant of this definition uses balls of radius ${\displaystyle cr}$ for some constant ${\displaystyle c>4}$. Choosing a constant greater than 4 implies additional structural properties of graphs of bounded highway dimension, which can be exploited algorithmically.^[5]

Definition 2

A subsequent definition^[6] of the highway dimension measures the sparseness of a hub set ${\displaystyle H}$ of shortest paths intersecting a ball of radius ${\displaystyle 2r}$:

The highway dimension of ${\displaystyle G}$ is the smallest integer ${\displaystyle h_{2}}$ such that for any radius ${\displaystyle r>0}$ and any node ${\displaystyle u\in V}$ there is a hitting set ${\displaystyle H\subseteq V}$ of size at most ${\displaystyle h_{2}}$ for all shortest paths ${\displaystyle P\in {\mathcal {P}}}$ of length more than ${\displaystyle r}$ and at most ${\displaystyle 2r}$ for which ${\displaystyle P\cap B_{2r}(u)\neq \emptyset }$.

This definition is weaker than the first, i.e., every graph of highway dimension ${\displaystyle h_{1}}$ also has highway dimension ${\displaystyle h_{2}}$, but not vice versa.^[5]

Definition 3

For the third definition^[7] of the highway dimension we introduce the notion of a "witness path": for a given radius ${\displaystyle r}$, a shortest path ${\displaystyle P\in {\mathcal {P}}}$ has an ${\displaystyle r}$-witness path ${\displaystyle Q\in {\mathcal {P}}}$ if ${\displaystyle Q}$ has length more than ${\displaystyle r}$ and ${\displaystyle Q}$ can be obtained from ${\displaystyle P}$ by adding at most one vertex to either end of ${\displaystyle P}$ (i.e., ${\displaystyle Q}$ has at most 2 vertices more than ${\displaystyle P}$ and these additional vertices are incident to ${\displaystyle P}$). Note that ${\displaystyle P}$ may be shorter than ${\displaystyle r}$ but is contained in ${\displaystyle Q}$, which has length more than ${\displaystyle r}$.

The highway dimension of ${\displaystyle G}$ is the smallest integer ${\displaystyle h_{3}}$ such that for any radius ${\displaystyle r>0}$ and any node ${\displaystyle u\in V}$ there is a hitting set ${\displaystyle H\subseteq V}$ of size at most ${\displaystyle h_{3}}$ for all shortest paths ${\displaystyle P\in {\mathcal {P}}}$ that have an ${\displaystyle r}$-witness path ${\displaystyle Q}$ with ${\displaystyle Q\cap B_{2r}(u)\neq \emptyset }$.

This definition is stronger than the above, i.e., every graph of highway dimension ${\displaystyle h_{1}}$ also has highway dimension ${\displaystyle h_{3}=O(h_{1}^{2})}$, but ${\displaystyle h_{1}}$ cannot be bounded in terms of ${\displaystyle h_{3}}$.^[5]

Shortest path cover

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 ${\displaystyle H}$, which is sparse in every ball:

Given a radius ${\displaystyle r>0}$, an ${\displaystyle r}$-shortest path cover of ${\displaystyle G}$ is a hitting set ${\displaystyle H\subseteq V}$ for all shortest paths in ${\displaystyle {\mathcal {P}}}$ of length more than ${\displaystyle r}$ and at most ${\displaystyle 2r}$. The ${\displaystyle r}$-shortest path cover ${\displaystyle H}$ is locally ${\displaystyle h}$-sparse if any node ${\displaystyle u\in V}$ the ball ${\displaystyle B_{2r}(u)}$ contains at most ${\displaystyle h}$ vertices of ${\displaystyle H}$, i.e., ${\displaystyle |B_{2r}(u)\cap H|\leq h}$.

Every graph of bounded highway dimension ${\displaystyle h}$ (according to any of the above definitions) also has a locally ${\displaystyle h}$-sparse ${\displaystyle r}$-shortest path cover for every ${\displaystyle r>0}$, but not vice versa.^[4] For algorithmic purposes it is often more convenient to work with one hitting set for each radius ${\displaystyle r}$, which makes shortest path covers an important tool for algorithms on graphs of bounded highway dimension.

Relation to other graph parameters

The highway dimension combines structural and metric properties of graphs, and is thus incomparable to common structural and metric parameters. In particular, for any graph it is possible to choose edge lengths such that the highway dimension is ${\displaystyle 1}$,^[5] while at the same time some graphs with very simple structure such as trees can have arbitrary large highway dimension. This implies that the highway dimension parameter is incomparable to structural graph parameters such as treewidth, cliquewidth, or minor-freeness. On the other hand, a star with unit edge lengths has highway dimension ${\displaystyle 1}$ (according to definitions 1 and 2 above) but unbounded doubling dimension, while a ${\displaystyle k\times k}$ grid graph with unit edge lengths has constant doubling dimension but highway dimension ${\displaystyle \Omega (k)}$.^[1] This means that the highway dimension according to definitions 1 and 2 is also incomparable to the doubling dimension. Any graph of bounded highway dimension according to definition 3 above, also has bounded doubling dimension.^[7]

Computing the highway dimension

Computing the highway dimension of a given graph is NP-hard.^[5] Assuming that all shortest paths are unique (which can be done by slightly perturbing the edge lengths), an ${\displaystyle O(\log h)}$-approximation can be computed in polynomial time,^[6] given that the highway dimension of the graph is ${\displaystyle h}$. 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 ${\displaystyle r}$ to the largest) nor top-down (from the largest value ${\displaystyle r}$ to the smallest).

Algorithms exploiting the highway dimension

Shortest path algorithms

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.^[7]

Approximations for NP-hard problems

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 ${\displaystyle r>0}$, an ${\displaystyle r}$-shortest path cover ${\displaystyle H}$ of ${\displaystyle G}$, and a vertex ${\displaystyle u\in V}$ at distance more than ${\displaystyle 2r}$ from ${\displaystyle H}$, the set ${\displaystyle T\subseteq V}$ of vertices at distance at most ${\displaystyle r}$ from ${\displaystyle u}$ according to the edge lengths ${\displaystyle \ell }$ is called a town. The set of all vertices not lying in any town is called the sprawl.

It can be shown that the diameter of every town is at most ${\displaystyle r}$, while the distance between a town and any vertex outside it is more than ${\displaystyle r}$. Furthermore, the distance from any vertex in the sprawl to some hub of ${\displaystyle H}$ is at most ${\displaystyle 2r}$.

Based on this structure, Feldmann et al.^[5] defined the towns decomposition, which recursively decomposes the sprawl into towns of exponentially growing values ${\displaystyle r}$. 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 (${\displaystyle 2-\varepsilon }$)-approximation on graphs of highway dimension ${\displaystyle O(\log ^{2}{n})}$,^[10] which implies that any (${\displaystyle 2-\varepsilon }$)-approximation algorithm needs at least double exponential time in the highway dimension, unless P=NP.^[10] On the other hand, it was shown that a parameterized ${\displaystyle 3/2}$-approximation algorithm with a runtime of ${\displaystyle 2^{O(kh\log {h})}n^{O(1)}}$ exists for k-Center where ${\displaystyle h}$ is the highway dimension according to any of the above definitions.^[10] When using definition 1 above, a parameterized approximation scheme (PAS) is known to exist when using ${\displaystyle k}$ and ${\displaystyle h}$ as parameters.^[11]

For the Capacitated k-Center problem there is no PAS parameterized by ${\displaystyle k}$ and the highway dimension ${\displaystyle h}$, unless FPT=W[1].^[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. But for Capacitated k-Center there is a PAS parameterized by ${\displaystyle k}$ and the doubling dimension.^[12]

External links

• Video on "Capacitated k-Center in Low Doubling and Highway Dimension"^[12] given by Tung Ahn Vu, 2022.
• Video on "Algorithms for Hard Problems on Low Highway Dimension Graphs" given by Andreas Emil Feldmann at ICERM, Brown University, Providence, US, May 2019.
• Video on "A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs"^[5] given by Andreas Emil Feldmann at Hausdorff Institut, Bonn, DE, 2015.
• Video on "Highway Dimension: From Practice to Theory and Back"^[6] given by Andrew Goldberg

References