## 4 Practice: Instance-Based Lower Bounds
### Generation of Witness Triples
#### 4.2.1 Method A: Fixed Lengths  
The high-level idea is as follows: We first compute and store all \(2n\) shortest path trees within the network (both forward and reverse). We then enumerate candidate shortest paths in increasing hop length (We define hop length as the number of nodes here). \(\ell=1,3,7,15,\dots\) (always doubling and adding 1) from the shortest path trees, greedily adding corresponding triples to \(W\) in case no conflict is created. As center node \(c\), we always choose the center node of a candidate path (in terms of hops), see, e.g., Figure 7a.  
This specific choice for \(c\) as well as the decision to always roughly double the lengths of the considered candidate paths was motivated by the observation in practice that when considering a candidate triple \((x,c,v)\), checking for conflict all triples \((.,.,v)\) and \((x,.,.)\) already present in \(W\) becomes quite expensive for large \(W\). Intuitively, the latter decision ensures that triples with different hop lengths can never be in conflict at all, the former that not too many triples with the same source or target are generated.  
Our actual greedy algorithm is stated in Algorithm 1. As we made sure that conflicts can only occur between triples with identical hop length, we can restrict the check for conflicts to the candidate set of triples of identical hop length. For an example of our greedy heuristic execution, look at the shortest path trees in Figure 7: Let us assume we  
Figure 7: Examples for witness triples in shortest path trees. (**a**) Forward shortest path tree \(SPT_{\rightarrow}(x)\): The witness triple \((x,c,v)\) where the relevant nodes for the conflict check are in the green bubble. There is no conflict with \((x,c,v^{\prime\prime})\) and its relevant nodes in the red bubble; (**b**) \(SPT_{\leftarrow}(v)\): The green witness triple \((x,c,v)\) of the left Figure shown in the backward tree of \(v\). It is in conflict with the blue triple \((x^{\prime},c,v)\) because they share the node \(c\).  
collected the set of candidates for length 3 which contains \((x,c,v)\), \((x,c,v^{\prime})\), \((x,c^{\prime},v^{\prime\prime})\), and \((x^{\prime},c,v)\) beside other triples. We now pick the candidate \((x,c,v)\) and add it to \(W\). Clearly, we remove this from our candidate set but we also have to remove \((x,c,v^{\prime})\) because it would lead to a conflict in the forward shortest path tree \(SPT_{\rightarrow}(x)\) and also remove \((x^{\prime},c,v)\) because of the conflict in the backward tree \(SPT_{\leftarrow}(v)\).  
Note that after computation of the shortest path trees, the collection of candidates can be organized in such a manner that each tree only needs to be traversed once. Moreover, the set of candidates can be subdivided over the shortest path trees and the center edges in buckets. As only candidates within one bucket need to be checked for conflicts, this leads to a reduced number of comparisons.  
Storing and computing the shortest path trees require \(\Theta(n^{2})\) space and \(\Omega(n(n\log n+m))\) time when using [PERSON]'s algorithm (here, \(m=|E|\)). Generation and pruning of candidate triples can be bounded by \(O(n^{3})\), yet in practice the computation of the shortest path trees clearly dominates the running time.