Highway dimension

The highway dimension is a

${\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}$,

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}$

doubling dimension

but highway dimension ${\displaystyle \Omega (k)}$.

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

${\displaystyle r}$

${\displaystyle r}$

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

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

parameterized ${\displaystyle 3/2}$-approximation algorithm

${\displaystyle 2^{O(kh\log {h})}n^{O(1)}}$

${\displaystyle h}$

${\displaystyle k}$

${\displaystyle h}$

For the Capacitated k-Center problem there is no PAS parameterized by ${\displaystyle k}$ and the highway dimension ${\displaystyle h}$, unless

parameterized by ${\displaystyle k}$ and the

• 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