# Foremost Walks and Paths in Interval Temporal Graphs +
## 3 NP-Hard Foremost Path and Walk Problems in Interval Temporal Graphs  
Several problems are known to be NP-hard for contact-sequence temporal graphs. For example, [PERSON] et al. (2014) show that computing several types of strongly connected components is NP-hard; [PERSON] et al. (2015) show that determining the existence of a no-wait path (In a no-wait path, the arrival and departure times at each intermediate vertex are the same.) between two vertices is NP-hard; and [PERSON] et al. (2016) show that computing several types of separators is NP-hard. Additional complexity results for contact-sequence temporal graphs appear in ([PERSON] et al., 2015). Since contact-sequence temporal graphs are a special case of interval-temporal graph, as discussed in Section 1, every problem that is NP-hard for the contact-sequence model remains NP-hard in the interval model. However, the reverse may not be true, as the transformation from the interval model to the contact-sequence model entails a possible explosion in the instance size. In this section, we demonstrate that \(mwf\) and \(mcf\) path and walk problems are NP-hard in the interval model but polynomially solvable in the contact-sequence model. In fact, in ([PERSON] et al., 2015), we show that finding a no-wait path from a given source vertex \(u\) to a destination vertex \(v\) in an interval-temporal graph whose underlying static graph (defined below) is acyclic is NP-hard and that this problem is polynomially solvable for contact-sequence graphs whose underlying static graph is acyclic. We remark in ([PERSON] et al., 2015) that our proof of this is easily extended to show that finding foremost, fastest, min-hop, and shortest no-wait paths in interval-temporal graphs with an acyclic underlying static graph is NP-hard while these problems are polynomial for contact-sequence temporal graphs whose underlying static graph is acyclic. The underlying _static graph_ for any contact-sequence temporal graph is the graph that results when each edge \((u,v,t,\lambda)\) is replaced by the edge \((u,v)\) and then multiple occurrences of the same edge \((u,v)\) are replaced by a single edge \((u,v)\). For an interval temporal graph, its underlying static graph is obtained by replacing each edge \((u,v,intvls)\) by the edge \((u,v)\). Figure 5 shows the underlying static graphs for the temporal graphs of Figures 1 and 2. We show below that finding \(mwf\) paths and walks and \(mcf\) paths is NP-hard for the interval model but polynomially solvable for the contact-sequence model (for acyclic graphs). \([M-M]\) or simply \([M]\)). The travel time for edge \((u_{i},u_{i+1})\) is \(s_{i}\), that for \((u_{n},v)\) is 1, and that for the remaining edges is 0. For every subset of \(S\), there is a no-wait path from \(u_{0}\) to \(u_{n}\) that arrives at \(u_{n}\) at a time equal to the sum of the \(s_{i}\)s in that subset. Further, every no-wait path from \(u_{0}\) to \(v\) must get to \(u_{n}\) at time \(M\). Hence, there is a no-wait path from \(u_{0}\) to \(v\) if \(S\) has a subset whose sum is \(M\). In addition, every time-respecting path from \(u_{0}\) to \(v\) in the temporal graph of Figure 6 is a foremost path, as there is no path from \(u_{0}\) to \(v\) that can arrive at \(v\) either before or after time \(M+1\). Hence, a min-wait foremost path from \(u_{0}\) to \(v\) has a total wait of 0 if there is a subset of \(S\) that sums to \(M\); this path gets to \(v\) at time \(M+1\). Hence, the min-wait foremost path problem is NP-hard. The same construction shows that the min-wait foremost walk problem is also NP-hard for interval temporal graphs as every walk in the graph of Figure 6 is a path. We note that the construction used in the above proof is easily modified, so that every edge has a travel time that is \(>\)0.