# Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs +
## 1 Introduction  
Temporal graphs are dynamic graphs that can change over time. Edges and Vertices in a temporal graph may evolve over time and thus have temporal information associated with them. Temporal graphs can be used to model many real-world problems such as modeling the spread of viral diseases, traffic flow in road networks, information flow in social networks and other such problems representing dynamic connectivity [1, 2, 3, 4, 5, 6, 7]. Recently, temporal graphs have been used in machine learning as temporal graph neural networks (\(TGN\)s) [8]. Different models can be used to represent a temporal graph [3]. One such popular model is a contact sequence temporal graph (\(CSG\)). Every instance of time when a communication can be initiated from a vertex \(u\) to a vertex \(v\) is represented by a unique temporal edge \((u,v,t,\lambda)\) in the \(CSG\) model. \(t\) is the departure time and \(\lambda\) is the travel time along this edge, such that the arrival time at \(v\) when departing \(u\) along this edge would be \(t+\lambda\). Figure 1 shows an example of a \(CSG\). An alternate representation of a temporal graph is an interval temporal graph (\(IT\)G). Temporal information on an edge connecting two vertices \((u,v)\) in an \(IT\)\(G\) is modeled as a vector of contiguous time intervals \(i=(s_{i},c_{i})\), with an associated travel time \(\lambda_{i}\) for each interval \(i\). Figure 2 illustrates an example of an \(IT\)\(G\). Communication from \(u\) to \(v\) may be initiated at any time \(t\) such that \(s_{i}\leq t\leq c_{i}\) for one of the intervals \(i\) along this edge. While every CSG has an equivalent ITG, the reverse is true only when time is discrete. Figure 1: Contact sequence temporal graph. Figure 2: Interval temporal graph. 1. _Intelligent Transportation Systems_--Road networks can be modeled by temporal graphs where vertices represent street intersections [9]. Varying traffic and street conditions are represented as temporal edges. Such temporal graphs enable building intelligence in transportation systems to improve safety, mobility and efficiency. 2. _E-health and bioinformatics_--Temporal graphs can be used to model pandemic spread by building proximity networks [10; 11; 12]. This kind of modeling can help understand the source of pandemic spread and the best methods to contain the pandemic spread. 3. _Social Networks_--Social networks are usually large dynamic graphs. Refs. [1; 13] present a framework for modeling social networks. [PERSON] et al. [5] propose an approach for studying temporal metrics in social graphs using temporal graphs. 4. _Artificial Intelligence_--Graph Neural Networks (GNNs) have become popular in recent times due to their ability to learn complex systems of relations or interactions. They provide a framework for deep learning models on graphs. Recently, new frameworks have been proposed for deep learning on dynamic or temporal graphs. For example, [PERSON] et al. [8] propose a framework for deep learning on temporal graphs that they call Temporal Graph Networks (TGNs). [PERSON] et al. [14] propose a novel architecture for online learning with temporal neural networks. Path and walk problems on temporal graphs are studied, for example, in [9; 15; 16; 17; 18; 19; 20]. While [16; 18; 19] focus on \(IT\)Gs, Refs. [15; 17; 20; 21] use the \(CSG\) model. [PERSON] et al. [15] demonstrate that the studied path problems can be solved faster using the algorithms proposed by them on the \(CSG\) representation when compared to the algorithms proposed on the \(ITG\) representation by [PERSON] et al. [16]. However, [PERSON] et al. [18; 19] subsequently developed algorithms for \(IT\)Gs that outperform the \(CSG\) algorithms of [PERSON] et al. [15] for most of the studied path problems as well as the ITG algorithms of [PERSON] et al. [16]. [PERSON] et al. [20] proposed an alternate TRG data structure for representing \(CSG\)s that results in faster algorithms than the algorithms of [PERSON] et al. [15] for most of the studied path problems. [PERSON] et al.