## 1 Introduction  
While the problem of computing the shortest paths in general graphs with non-negative edge weights seems to have been well understood already decades ago, the last 10-15 years have seen tremendous progress when it comes to the specific problem of efficiently computing shortest paths in _real-world road networks_. Here, the idea is to spend some time for preprocessing where auxiliary information about the network is computed and stored, such that subsequent queries can be answered much faster than standard [PERSON]'s algorithm. One might classify most of the employed techniques into two classes: ones that are based on _pruned graph search_ and others that are based on _distance lookups_. Most approaches fall into the former class, e.g., reach-based methods [1, 2], highway hierarchies [3], arc-flags-based methods [4], or contraction hierarchies (CH) [5]. Here, [PERSON]'s algorithm is given a hand to ignore some vertices or edges during the graph search. The speed-up for road networks compared to plain [PERSON]'s algorithm ranges from one up to three orders of magnitude [1, 5]. In practice, this means that a query on a country-sized network like that of Germany (~20 million nodes) can be answered in less than a _millisecond_ compared to few seconds of [PERSON]'s algorithm. While these methods directly yield the actual shortest path, the latter class is primarily concerned with the computation of the (exact) distance between given source and target--recovering the actual path often requires some additional effort. Examples of such distance-lookup-based methods are transit nodes [6, 7] and hub labels (HL) [8]. They allow for the answering of _distance queries_ another one or two orders of magnitude faster. There have also been attempts at theoretically explaining the impressive practical performance of these speed-up schemes. These approaches first identify certain properties of a graph, which supposedly characterize \"typical\" inputs in the real-world and then show that for graphs satisfying these properties, certain speed-up schemes have guaranteed query/construction time or space consumption. Examples of such graph characterizations are given via _highway dimension_[9], _skelton dimension_[10], or _bounded growth_[11]. Note that these approaches are all concerned with _upper bounds_. For example, in [9] it is shown that for graphs with highway dimension \(h\), after a preprocessing step, the number of considered nodes during a CH query is \(O(h\log n)\), which for polylogarithmic \(h\) is polylogarithmic in the network size. While small (i.e., constant or polylogarithmic) highway dimension is often assumed for real-world networks, note that even a simple \(\sqrt{n}\times\sqrt{n}\) grid has highway dimension \(h=\Theta(\sqrt{n})\), so the upper bound guaranteed by [9] is \(O(\sqrt{n}\log n)\). Similarly, an analysis based on the bounded growth property [11] shows an upper bound of \(O(\sqrt{n}\log n)\). In this work, we are concerned with two specific speed-up techniques: contraction hierarchies [5] and hub labels [8], and we provide _lower bounds_. As grid-like substructures are quite common in real-world road networks (see Figure 1), one might ask whether better upper bounds for such networks are impossible in general or whether a polylogarithmic upper bound could be shown via more refined proof or CH construction techniques. Our work settles this question for contraction hierarchies as well as hub labels up to a logarithmic factor. We show that for CH, no matter what contraction order is chosen, and for HL, no matter how the hub labels are generated, there are grid networks for which not only the worst-case but even the _average_ number of nodes to be considered during a query (which we call _search space_) is \(\Omega(\sqrt{n})\). The insights of our theoretical lower bound analysis also allow us to devise a scheme to compute _instance-based_ lower bounds, that is, for a given concrete road network, we algorithmically compute a lower bound on the average search space size.