Disjoint Temporal Walks Under Waiting Time Constraints

A temporal (directed) graph is a (directed) graph whose edge availability varies over time, and temporal walks are sequences of adjacent edges respecting these availabilities. A third component of this scenario imposes time constraints on the vertices, known as “waiting time constraints.” Drawing a parallel with a transportation network, these constraints can be envisioned as the minimum and maximum time a person would need or be willing to stay at the same location. It is known that computing a temporal walk between a pair of vertices under waiting time constraints can be achieved in polynomial time, even when optimizing certain criteria. In this article, we extend these investigations to the problem of finding k temporal walks such that no two distinct walks overlap in time. Given a multiset {(s1,z1),…,(sk,zk)} of pairs of vertices of a temporal graph G, we consider the problem of finding a set of pairwise temporally disjoint walks P1,…,Pk such that each Pi is a temporal walk from si to zi. Under a given set of waiting time constraints, when si=s and zi=z for all i∈[k] we show that determining the existence of such walks is W[1]-hard when parameterized by k, and that it is NP-complete to decide the existence of a separator (i.e., a set of vertex occurrences in time intersecting all such walks) of size at most h. In the more general case, when the vertices si and zi are allowed to be disjoint, we show that the walks can be found in XP time parameterized by k when each walk has to wait at least ωL(u)≥1 units of time on each occurrence of each vertex u used by the walk, and that the separator can be found in XP time with parameter h.