# Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs +
## 2 Problem Description  
### Definitions  
**Definition 1** (Contact sequence temporal graph). : _In a contact sequence temporal graph \(G=(V,E)\), each edge \(e\in E\) is a tuple \((u,v,t,\lambda)\), where \(t\) is a permissible departure time for travel from \(u\) to \(v\) along the edge \(e\) and \(\lambda\) is the amount of time it takes to travel on edge \(e\) from \(u\) to \(v\) when departing at time \(t\). Thus, \(v\) is reached at time \(t+\lambda\). If there are \(m\) time instances when departures from \(u\) to \(v\) are permissible, there will be \(m\) such temporal edges \([(u,v,t_{1},\lambda_{1});(u,v,t_{2},\lambda_{2})\ldots;(u,v,t_{m},\lambda_{m})]\). \(m\) is the amount of activity on the connection \((u,v)\)._  
**Definition 2** (Interval temporal graphs). : _In an interval temporal graph \(G=(V,E)\), each edge \(e\in E\) is represented by a tuple \((u,v,intvls)\). This tuple represents a connection from \(u\) to \(v\). intvls is a time-ordered non-overlapping vector of tuples \([(s_{1},c_{1},\lambda_{1});(s_{2},c_{2},\lambda_{2});\ldots;(s_{n},c_{n}, \lambda_{n})]\). The \(i\)th interval starts at time \(s_{i}\) and closes (ends) at time \(c_{i}\); \(\lambda_{i}\) is the time it takes to traverse the edge when departing \(u\) at a time \(t\) if \([s_{i}\leq t\leq c_{i}]\) (\(v\) is reached at time \(t+\lambda_{i}\)). The intervals are in ascending order of start times \(s_{i}\), and collectively, they define the permissible departure times from \(u\)._  
The permissible travel intervals for any edge of an \(ITG\) (Definition 2) can be adjusted such that for any two consecutive intervals \([(s_{i},c_{i},\lambda_{i});(s_{i+1},c_{i+1},\lambda_{i+1})]\) we have \((c_{i}+\lambda_{i}\leq s_{i+1}+\lambda_{i+1})\). This transformation is explained in [PERSON] and [PERSON] [18]. In this paper, we assume that the intervals associated with each edge of an \(ITG\) satisfy this constraint. As is evident from Figures 3 and 4, a given temporal graph may need a much larger number of edges to be expressed as a \(CSG\) versus an \(ITG\). This is especially true when the graph has large contiguous travel intervals on the edges. [PERSON] et al. [18] demonstrated that several temporal path and walk problems on \(CSG\)s may be polynomial in the size of the input graph but NP-hard for the equivalent \(ITG\) graph. Figure 4: High-activity contact sequence graph. Figure 3: Interval temporal graph with large intervals. **Definition 3** (Temporal paths and walks). : _A path (equivalently, valid path, feasible path, temporal path or time-respecting path), \(p=\{u_{1},t_{1},u_{2},t_{2},...,u_{k}\}\), in a temporal graph is an alternating sequence of vertices and departure times from those vertices starting from a source vertex \(u_{1}\) to a destination vertex \(u_{k}\) such that no vertex appears more than once in this sequence. \(t_{i}\) is a permissible departure time from \(u_{i}\) to \(u_{i+1}\) and \((t_{i}+\lambda_{i})\leq t_{i+1}\), \(1\leq i<k\). \((t_{i}+\lambda_{i})\) is the arrival time at \(u_{i+1}\) when departing \(u_{i}\) at \(t_{i}\), \(1\leq i<k\). For path \(p\), \(u_{1}\) is the source or start vertex and \(u_{k}\) is the destination vertex. The number of hops is \(k-1\). When vertices are permitted to repeat in \(p\), \(p\) is a walk. Note that every path is also a walk but some walks are not paths._  
**Definition 4** (Shortest paths). : _A shortest path \(p\) in a temporal graph is a feasible temporal path from a start vertex \(u_{1}\) to a destination vertex \(u_{k}\) with minimum length, where the length, \(len(p)\), of a path \(p\) is the sum of the travel times \(\lambda_{i}\) on the edges \(e_{i}\) on this path._  
\[len(p)=\sum_{i=1}^{k-1}\lambda_{i} \tag{1}\]  
By contrast, a fastest path from \(u_{1}\) to \(u_{k}\) is a temporal path that minimizes the difference between the arrival time at \(u_{k}\) and the departure time from \(u_{1}\). Such a path accounts for wait times at all intermediate vertices.