Chapter 6

Contraction Hierarchy Theory

In this chapter, we examine how to determine an effective contraction order for the nodes of a graph. A well chosen order minimizes the number of shortcut edges introduced during contraction, which in turn reduces both query time and memory usage. Excessive shortcut edges increase the size of the contracted graph and slow down routing queries, so our goal is to keep the number of such edges as small as possible ideally maintaining memory usage that is linear in the size of the input graph.

Worked Example

The example below illustrates how the contraction order impacts the number of shortcut edges. First, consider contracting the graph in the order E, D, C, B, A.

Contracting node E first leads to the creation of 12 shortcut edges. In contrast, reversing the order—contracting A, B, C, D, E, adds no shortcuts at all.

Highway Dimension

From a theoretical perspective, analyzing the efficiency of Contraction Hierarchies is much more interesting when some limited assumptions about the graph can be made. For instance, contraction hierarchies provides no asymptotic improvement over classical routing algorithms on dense graphs such as the complete graph. However, real world road networks exhibit special structure that contraction hierarchies can exploit. One formalization of this structure is the concept of Highway Dimension, introduced by [Abraham2016, page 6].

A graph has highway dimension $h$ if, for every radius $r$ and every vertex $v$, all shortest paths of length between $r$ and $2r$ that pass through the ball of radius $2r$ centered at $v$ can be intersected by at most $h$ access vertices. These access vertices "hit" all such long paths, ensuring coverage with a small, localized set.

Theoretical Results for contraction hierarchies with Low Highway Dimension

Assuming that the input graph has small highway dimension $h$, [Abraham2016, page 12] propose a method for constructing contraction hierarchies with provable efficiency. They introduce sparse path hitting sets (SPHS) at multiple scales. For each scale $r = 2^i$, a small set of nodes is chosen to cover all long paths in their vicinity. These sets are organized into hierarchical levels $Q_i$, where lower levels contain less important nodes that are contracted first.

This construction yields the following theoretical guarantees [Abraham2016, page 12]. Let $h$ be the highway dimension of the input graph, $V$ be the number of vertices and $D$ the diameter of the graph.

1. The total number of edges in the contraction hierarchy is bounded by $\mathcal{O}(V \cdot h \cdot \log D)$
2. The degree of any vertex in the contraction hierarchy is bounded by $h + h \cdot \log D$.
3. Query time for shortest paths using the contraction hierarchy is $\mathcal{O}((h \cdot \log D)^2)$.

These results show that, for graphs with small highway dimension, contraction hierarchies with efficient overall size exist.

Note however that the above bounds rely on being able to compute sparse path hitting sets, which is not currently known to be computable in polynomial time. If one uses an appaoximation instead (in order to compute the contraction hierarchy in polynomial time) the factors change as follows [Abraham2016, pages 16-17]:

1. The total number of edges in the contraction hierarchy is bounded by $\mathcal{O}(V \cdot h \cdot \log h \cdot \log D)$
2. The degree of any vertex in the contraction hierarchy is bounded by $h \cdot \log h \cdot \log D$.
3. Query time for shortest paths using the contraction hierarchy is $\mathcal{O}((h \cdot \log h \cdot \log D)^2)$.

Practical Considerations

While theoretically sound, constructing SPHS hierarchies is computationally expensive, albeit polynomial in $V$. In practice, heuristic methods are preferred for their efficiency, even though they may lack provable guarantees.

Our implementation is based on the [FastPaths] library, which uses a heuristic approach. It assigns each vertex an importance score based on local graph structure and connectivity. This method achieves high performance in practice and aligns with the observed efficiency of contraction hierarchies in real world road networks.