# Dynamic Shortest Paths Methods for the Time-Dependent TSP
## 2 Complexity  
As a generalization of the TSP, the TDTSP is \(\mathcal{NP}\)-hard itself. Recall that while there exists no \(\alpha\)-approximation for any \(\alpha>1\) for the general TSP, the metric TSP can be approximated [29] (p. 557). This does not hold for the metric TDTSP:  
Theorem 2.1: _There is no \(\alpha\)-approximation algorithm for any \(\alpha>1\) for the TDTSP unless \(\mathcal{P}=\mathcal{NP}\), even if the FIFO property and the time-dependent triangle inequality are satisfied._  
Proof: Suppose there exists an \(\alpha\)-approximation algorithm Alg for some \(\alpha\geq 1\). We show that algorithm Alg could be used to solve the Hamiltonian Cycle problem on an undirected graph \(G=(V,E)\). To this end, let \(D=(V,A)\) be the bidirected complete graph with costs  
\[d_{uv}\coloneqq \begin{cases}1&\text{if $\{u,v\}\in E$, and}\\ 2&\text{otherwise.}\end{cases} \]  
Note that \(G\) is Hamiltonian if, and only if \(D\) contains a tour with costs of exactly \(n\) with respect to the cost function \(d\). Let \(M\coloneqq\lceil\alpha n\rceil+1\), \(s\in V\) be an arbitrary source vertex, and \(\theta^{\max}\coloneqq n\cdot M\) be a time horizon. For \(\theta\in\Theta\) and \(a\in A\), let  
\[c_{uv}(\theta)\coloneqq \begin{cases}M&\text{if $(v,\theta,d_{uv})=(s,n-1,2)$ or $\theta>n$, and}\\ d_{uv}&\text{otherwise}\end{cases}  \tag{2}\]  
be a set of time-dependent cost functions. These cost functions satisfy both the FIFO property and the time-dependent triangle inequality (1). We distinguish two cases with respect to the TDTSP instance \((D,c,s,\theta^{\max})\):  
* \(G\) has a Hamilton cycle, and therefore, a tour \(T=(a_{1},\ldots,a_{n})\) with costs of \(n\) exists in \(D\): In this case, the values \(d(a_{i})\) for \(i=1,\ldots,n\) are all equal to one, implying that the optimal solution to the TDTSP instance has an arrival time of \(n\). Alg yields a tour \(T_{\text{apx}}\) with an arrival time of, at most, \(\alpha n<M\). Consequently, the first case of (2) is never attained, implying that each arc has a travel time of one, and Alg correctly identifies a Hamiltonian cycle in \(G\). * \(G\) does not possess a Hamiltonian cycle, and every tour \(T=(a_{1},\ldots,a_{n}=(u,s))\) has a cost of at least \(n+1\) with respect to \(d\): As a result, there must be one arc \(a_{k}\in T\) having a travel time of at least two. If \(k<n\), then \(T\) arrives at \(u\) at time \(\theta\geq n\), and the travel time of \(a_{n}\), and consequently the arrival time of \(T\) is at least \(M\). If, on the other hand, \(k=n\), then \(T\) arrives at \(u\) at time \(n-1\) and arc \(a_{n}\) has a travel time of more than one, which is only possible if \(d_{uv}=2\), yielding a travel time of \(M\) for \(a_{n}\). In any case, the arrival time of \(T\) is at least \(M>\alpha n\). Based on this distinction, \(G\) has a Hamilton cycle if, and only if Alg produces a tour with an arrival time of \(n\). Remark 1 (Dynamic Programming): _It is well-known [30] that the (asymmetric) TSP can be solved by using a dynamic programming approach. Let \(C(S,v)\) be the smallest cost of an \((s,v)\)-path consisting of the vertices \(S\subseteq V\) with \(s,v\in S\), and \(s\
eq v\). Then, \(C(S,v)\) satisfies the following recursive relationship:_  
\[C(\{s,v\},v) =c_{sv} \forall\,v\in V,v\
eq s\] \[C(S,v) =\min_{ \begin{subarray}{c}u\in S\\ u\
eq s,v\end{subarray} }C(S\setminus\{v\},u)+c_{uv} \forall\,S\subseteq V,|S|\geq 3,v\in S.\]  
_The cost of an optimal tour is then given by \(\min_{v\
eq s}C(V,v)+c(v,s)\), and can be determined by computing the values \(C(S,v)\) in increasing order of \(|S|\), yielding an \(\mathcal{O}(2^{n}\cdot n^{2})\) algorithm for the ATSP.__In order to adapt the approach to the TDTSP, we can define \(C(S,v)\) as the minimum arrival time of any \((s,v)\)-path departing from \(s\) at \(\theta=0\), consisting of the vertices \(S\subseteq V\) with \(s,v\in S\) and \(s\
eq v\).