Parameterized Restless Temporal Path

doi:10.1007/978-3-032-04700-7_7

Return

Parameterized Restless Temporal Path

2026-01-01

PRE

Justine Cauvi *

Laurent Viennot

DOI：10.1007/978-3-032-04700-7_7

Original

Original request for help

Save

Abstract

En 中文

Recently, Bumpus and Meeks introduced a purely temporal parameter, called vertex-interval-membership-width, which is promising for the design of fixed-parameter tractable (FPT) algorithms for vertex reachability problems in temporal graphs. We study this newly introduced parameter for the problem of restless temporal paths, in which the waiting time at each node is restricted. In this article, we prove that, in the interval model, where arcs are present for entire time intervals, finding a restless temporal path is NP-hard even if the vertex-interval-membership-width is equal to three. We exhibit FPT algorithms for the point model, where arcs are present at specific points in time, both with uniform delay one and arbitrary positive delays. In the latter case, this comes with a slight additional computational cost.

Keywords:

Temporal graphs

Restless temporal paths

Parameterized algorithms

Interval-membership-width