## 4 Practice: Instance-Based Lower Bounds
### Experimental Results  
We implemented our witness search heuristics in C++ and evaluated it on several graphs. Besides a very small _test graph_ for sanity checking, we extracted real-world networks graphs based on Open Street Map (OSM) data for our main experiment. We picked _Lower Manhattan_ to get a grid-like graph. For the street network of the German federal city-state _Bremen_, we created a large version _car_ which includes all streets passable by car, as well as the versions _fast car_ and _highway_ only containing streets allowing at least a speed of 50 km/h and 130 km/h, respectively. The code was run on a 24-core Xeon(R) CPU E5-2650v4, 768 GB RAM machine. To assess the quality of our lower bounds, we constructed a CH where the contraction order was defined by the so called _edge-difference_ heuristic, that is, nodes that introduce few additional shortcuts are contracted first. This is one of the most popular contraction order heuristics. From this CH, we calculated the average \(|DSS|\) (forward + backward) and compared it with the lower bounds computed by our two methods. In Table 1, we list our results. Compared to our original paper [18], we realized that we can collect one more triple for every node due to a technicality which is described in more detail in Section 5.2. We updated the experiment results accordingly. Our biggest graph has over a quarter of a million edges and almost 120 k nodes. As expected, the space consumption is quadratic which makes our current algorithm infeasible for continental-sized networks. For the large Bremen graph, our 24-core machine took 32.5 h to complete the lower bound construction via our greedy heuristic and used 354 GB of RAM. Most important is the quotient \(\frac{LB}{|DSS|}\) which gives us a hint about the quality of our computed lower bound: For the _highway_ version of Bremen, we achieve even 96%, that is, the average search spaces in the computed CH are guaranteed to be less than a factor of 1.05 above the optimum. Note, however, that this graph is atypical for road networks in the sense that it is far from being fully connected. The value of \(\frac{LB}{|DSS|}\) decreases for our bigger graphs down to around 30%. The decrease can have several reasons: On one hand, our CH is based on a heuristic and is not necessarily optimal (no optimal algorithm is known), so even if we had brute-forced a maximum sized triple-set we would most certainly not achieve 100%. Indeed, our contribution is to show that the gap between the heuristic and the perfect is at most \(1-\frac{LB}{|DSS|}\). On the other hand, the results strongly indicate that the missing of some long triples which do not have a length of \(2^{i}\) becomes more relevant in bigger graphs. Note that it could also mean that the edge-difference heuristic performs worse on bigger graphs. It has been shown that constructing the optimal CH (even though according to a different optimality criterion) is NP-hard, see in [16], so we actually conjecture that finding the largest conflict-free set of triples would also turn out to be NP-hard if investigated further. Our alternative method B for generating witness triples consistently fares worse in terms of the constructed lower bound, but requires very little space. It remains to see whether a more elaborate order of considering witness candidates leads to better results, or if a different underlying contraction hierarchy (which determines in which order to enumerate the center points) makes a big difference. In another experiment, we generated lightheaded grids graphs and tested them with our method A. The results can be seen in Table 2. According to expectations, the average search space is growing linearly with the side length of the grid. Fulfilling the intentions of its construction, the average search space of a lightheaded grid is quite high in comparison to real world grids: for a side length of 20, i.e., only 400 nodes in total, the search space size is close to the one of the much bigger real world graph _bremen (car)_ with almost 120 k nodes.