  Computing a (short) path between two vertices is one of the most fundamental
primitives in graph algorithmics. In recent years, the study of paths in
temporal graphs, that is, graphs where the vertex set is fixed but the edge set
changes over time, gained more and more attention. A path is time-respecting,
or temporal, if it uses edges with non-decreasing time stamps. We investigate a
basic constraint for temporal paths, where the time spent at each vertex must
not exceed a given duration $\Delta$, referred to as $\Delta$-restless temporal
paths. This constraint arises naturally in the modeling of real-world processes
like packet routing in communication networks and infection transmission routes
of diseases where recovery confers lasting resistance. While finding temporal
paths without waiting time restrictions is known to be doable in polynomial
time, we show that the "restless variant" of this problem becomes
computationally hard even in very restrictive settings. For example, it is
W[1]-hard when parameterized by the distance to disjoint path of the underlying
graph, which implies W[1]-hardness for many other parameters like feedback
vertex number and pathwidth. A natural question is thus whether the problem
becomes tractable in some natural settings. We explore several natural
parameterizations, presenting FPT algorithms for three kinds of parameters: (1)
output-related parameters (here, the maximum length of the path), (2) classical
parameters applied to the underlying graph (e.g., feedback edge number), and
(3) a new parameter called timed feedback vertex number, which captures
finer-grained temporal features of the input temporal graph, and which may be
of interest beyond this work.
