## 4 Practice: Instance-Based Lower Bounds
### Witness Triples  
In our lower bound proof for the lightheaded grid, we identified pairs \((x,v)\) such that \(v\in DSS(x)\), making use of a concrete (but arbitrary) CH (or HL) for the lightheaded grid to actually identify those pairs \((x,v)\). We cannot do this for a given instance of a road network, since we would have to consider all possible CH/HL constructions. Therefore, instead of pairs \((x,v)\) let us now try to identify _witness triples_\((x,c,v)\) where \(c\) is again a node on the (directed) shortest path from \(x\) to \(v\). The intuition for \((x,c,v)\) is the following: On the shortest path \(\pi(x,v)=x\ldots c\ldots v\), some node of the suffix \(c\ldots v\) of \(\pi\) must be in the forward search space of \(x\), or some node on the prefix \(x\ldots c\) must be in the backward search space of \(v\). This intuition mimics the proof idea in the previous section but also allowing for _directed_ graphs and leaving the choice \(c\) open.  
In the following, we sometimes treat paths just as sets of nodes to simplify presentation. Let us first define the notion of a conflict between two triples.  
**Definition 1** (conflict between triples).: _We say two triples \((x,c,v)\) and \((x^{\prime},c^{\prime},v^{\prime})\) are in conflict if at least one of the following conditions holds true:_  
1. \(x=x^{\prime}\) _and_ \(\pi(c,v)\cap\pi(c^{\prime},v^{\prime})\
eq\emptyset\)__
2. \(v=v^{\prime}\) _and_ \(\pi(x,c)\cap\pi(x^{\prime},c^{\prime})\
eq\emptyset\)__  
See Figure 6(a) for a non-conflicting and Figure 6(b) for a conflicting example. Our goal will be to identify an as large as possible set \(W\) of _conflict-free_ witness triples. The following Lemma proves that the size of such a set \(W\) lower bounds the average search space and label size.  
**Lemma 3**.: _If \(W\) is a set of conflict-free witness triples, then \(|W|\) lower bounds the sum of (backward and forward) search spaces of all nodes in the network._  
Proof.: Consider a triple \((x,c,v)\) and the following two cases:  
1. it accounts for a node in \(\pi(c,v)\) in the forward search space of \(x\). Nodes in the forward search space of \(x\) can only be accounted for by triples \((x,c^{\prime},v^{\prime})\). However, as \(\pi(c,v)\cap\pi(c^{\prime},v^{\prime})=\emptyset\) due to \(W\) being conflict-free, we have not doubly accounted for it.
2. it accounts for a node in \(\pi(x,c)\) in the backward search space of \(v\). Nodes in the backwards search space of \(v\) can only be accounted for by triples \((x^{\prime},c^{\prime},v)\). However, as \(\pi(x,c)\cap\pi(x^{\prime},c^{\prime})=\emptyset\) due to \(W\) being conflict-free, we have not doubly accounted for it.  
For any witness set \(W\), \(|W|/(2n)\) yields a lower bound on the average size of an in- or outlabel in case of the HL scheme, and on the average size of the direct search space from a single node in case of the CH scheme.  
Therefore, it remains to compute a large conflict-free witness set \(W\). Theoretically, one could enumerate all potential triples, build the conflict graph and use Integer Linear Programming (ILP) techniques to identify a conflict-free subset among the triples. A similar approach was conducted in [17] to compute lower bounds for transit nodes constructions.  
However, enumerating all potential triples in \(V\times V\times V\) here seems somewhat inefficient (having to inspect \(\Theta(n^{3})\) such triples) on its own and employing the ILP techniques on top of it even more so. Therefore, in the following we propose a simple greedy heuristic. Again, let us emphasize that the resulting lower bound holds for _any_ CH/HL construction for the given road network.