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

1. Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. (2010-01-17). Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. Society for Industrial and Applied Mathematics. pp. 782–793. doi:10.1137/1.9781611973075.64. ISBN   978-0-89871-701-3. S2CID   9330775.
2. Bast, Holger; Funke, Stefan; Matijevic, Domagoj; Sanders, Peter; Schultes, Dominik (2007-01-06), Applegate, David; Stølting Brodal, Gerth (eds.), "In Transit to Constant Time Shortest-Path Queries in Road Networks", 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 46–59, doi: 10.1137/1.9781611972870.5 , ISBN   978-1-61197-287-0 , retrieved 2023-11-10
3. Bast, Holger; Funke, Stefan; Matijevic, Domagoj; Demetrescu, Camil; Goldberg, Andrew; Johnson, David (2006). "TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing". The Shortest Path Problem: Ninth DIMACS Implementation Challenge.
4. Blum, Johannes (2019). "Hierarchy of Transportation Network Parameters and Hardness Results". Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi:10.4230/LIPIcs.IPEC.2019.4. S2CID   166228480.
5. Feldmann, Andreas Emil; Fung, Wai Shing; Könemann, Jochen; Post, Ian (January 2018). "A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs". SIAM Journal on Computing. 47 (4): 1667–1704. doi:10.1137/16M1067196. ISSN   0097-5397. S2CID   11339698.
6. Abraham, Ittai; Delling, Daniel; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. (2011). "VC-Dimension and Shortest Path Algorithms". In Aceto, Luca; Henzinger, Monika; Sgall, Jiří (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 6755. Berlin, Heidelberg: Springer. pp. 690–699. doi:10.1007/978-3-642-22006-7_58. ISBN   978-3-642-22006-7.
7. Abraham, Ittai; Delling, Daniel; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. (2016-12-08). "Highway Dimension and Provably Efficient Shortest Path Algorithms". Journal of the ACM. 63 (5): 41:1–41:26. doi:10.1145/2985473. ISSN   0004-5411. S2CID   1943037.
8. Blum, Johannes; Disser, Yann; Feldmann, Andreas Emil; Gupta, Siddharth; Zych-Pawlewicz, Anna (2022). "On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension". Proceedings of 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi:10.4230/LIPIcs.IPEC.2022.5.
9. Feldmann, Andreas Emil; Saulpic, David (2021-12-01). "Polynomial time approximation schemes for clustering in low highway dimension graphs". Journal of Computer and System Sciences. 122: 72–93. doi:10.1016/j.jcss.2021.06.002. ISSN   0022-0000.
10. Feldmann, Andreas Emil (2019-03-01). "Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs". Algorithmica. 81 (3): 1031–1052. doi:10.1007/s00453-018-0455-0. ISSN   1432-0541.
11. Becker, Amariah; Klein, Philip N.; Saulpic, David (2018). "Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension". Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018). Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi:10.4230/LIPIcs.ESA.2018.8.
12. Feldmann, Andreas Emil; Vu, Tung Anh (2022). Bekos, Michael A.; Kaufmann, Michael (eds.). "Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension". Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science. Cham: Springer International Publishing: 215–229. doi:10.1007/978-3-031-15914-5_16. ISBN   978-3-031-15914-5.