Sie sind hier

# The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints

Philipp Zschoche (TU Berlin)

Computing a (shortest) path between two vertices in a graph is one of the most fundamental primitive in graph algorithms. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set remains static but the edge set may change over time, gained more and more attention. Such a path is time-respecting, or simply temporal, if it uses time edges that have non-decreasing time stamps. The computation of temporal paths is known to be polynomial-time feasible for several optimality criteria such as minimizing the arrival time, the number of hops, or the duration of the path. A natural constraint when computing a temporal path is to limit the time it is allowed to pause at a vertex; such a constraint arises naturally in the modeling of infectious diseases and communication networks.

In this paper, we investigate the computational cost of finding temporal paths whose waiting time at each vertex is bounded by some duration Δ, referred to as Δ-restless temporal paths. Interestingly, this problem turns out to be computationally hard even in very restrictive settings. In particular, it is NP-hard even when the lifetime of the graph spans only three time steps (with Δ=1), and we show that it is W[1]-hard when parametrized by a wide range of parameters of the underlying graph. On the positive side, we show that the problem is FPT when parametrized either by the feedback edge set of the underlying graph, or by the number of hops of the solution, the algorithm for the latter being asymptotically optimal under the Exponential Time Hypothesis. Finally, we discuss several ways to parametrize temporal graph instances in general and introduce a new parameter to this effect.


Date
Speaker
Location
Language
06.02.2020
16:15
Philipp Zschoche
TEL 512
English

Back to the research colloquium site.

To top