# Dynamic Shortest Paths Methods for the Time-Dependent TSP
## Appendix A Time-Dependent Spanning Trees
The travel time of the edge connecting \(x_{ik}\) and \(v_{ik}\) depends on whether \(x_{k}\) or \(\overline{x}_{k}\) appears in the clause \(Z_{j}\). In the former case the travel time is constantly 1, whereas in the latter it is given by \[c_{x_{ik}v_{ik}}(\theta)\coloneqq \begin{cases}0&\text{if $\theta\geq 2$, and}\\ 2&\text{otherwise.}\end{cases} \] The instance including the components, depicted in Figure 10, has a TDMST of cost less than \(M\) if and only if the 3 SAT instance is satisfiable:  
Consider a satisfying truth assignment of the 3 Sat instance. For each variable \(x_{j}\) set to true we choose the path \((s,s_{j},x_{j},t_{j})\) in component \(A_{j}\). If the variable is set to false we choose the path \((s,s_{j},t_{j},x_{j})\) to be part of the spanning tree. Thus, the arrival time of the tree at \(x_{j}\) is 1 if \(x_{j}\) is set to true and 2 otherwise. For each clause \(Z_{i}\) we add the edges between the vertices corresponding to its variables and their respective \(v_{i}\) counterparts. Since the clause is satisfied, the arrival time at one of \(v_{i1}\), \(v_{i2}\), or \(v_{i3}\) is at most 2, enabling us to add the edges \(\{v_{ik},w_{ik}\}\), \(\{w_{i1},w_{i2}\}\), and \(\{w_{i2},w_{i3}\}\) at a cost of 1 each. The total cost of the resulting tree is at most \(2n+6m<M\). Conversely, consider a tree \(T\) with costs less than \(M\). We first consider the \((s,s_{j})\)-paths in \(T\) for all \(j=1,\ldots,n\). If this path does not contain \(\{s,s_{j}\}\) itself, then it must start by t traversing a variable gadget \(A_{j^{\prime}}\) for \(j^{\prime}\
eq j\) continued by a clause gadget \(B_{i}\), entering via \(v_{ik}\) and leaving via \(v_{il}\). As was established above, the earliest arrival time at \(v_{ik}\) is 2, implying that the time of arrival at \(w_{il}\) is at least 4, resulting in a travel time of at least \(M\) for the traversal of edge \(\{w_{il},v_{il}\}\), thereby contradicting the assumption of \(c(T)<M\). For the same reason, \(T\) must contain either the path \((s,s_{j},x_{j})\) or \((s,s_{j},t_{j},x_{j})\). Based on the optimality of \(T\), the tree must contain \((s,s_{j},x_{j},t_{j})\) in the former case. We can therefore identify the choice of paths with a variable assignment as we did above. To see that the assignment is feasible, we note that for each clause \(Z_{i}\) one of the edges \(\{v_{ik},w_{ik}\}\), say \(\{v_{i1},w_{i1}\}\), is in \(T\) and directed away from \(v_{i1}\). Since \(c(T)<M\), the travel time of this edge must be less than \(M\), implying that the arrival time of \(T\) at \(v_{i1}\) is at most 2. If \(x_{i1}\) appears in \(Z_{j}\), then the arrival time at \(x_{i1}\) is 1, and the variable is set to true satisfying \(Z_{i}\). If \(\overline{x}_{i1}\) appears in \(Z_{j}\), then it follows that the arrival time at \(x_{i1}\) is 2, the variable is set to false and clause \(Z_{i}\) is satisfied as well. Now assume the existence of an \(\alpha\)-approximation for the TDMST problem. We construct the instance introduced above for \(M\coloneqq\lceil\alpha\cdot(2n+6m)\rceil\) and apply the approximation. If the resulting tree has costs less than \(M\), the 3 SAT instance is satisfiable. Otherwise, the optimal TDMST has costs at least \(M/\alpha\geq 2n+6m\), and the instance is not satisfiable.