标题： 参数化无休止时间路径 显示英文标题

标题： Parameterized Restless Temporal Path

摘要： 最近，Bumpus 和 Meeks 引入了一个纯时间参数，称为顶点区间成员宽度，这在设计针对时间图中顶点可达性问题的固定参数可解（FPT）算法方面具有前景。 我们研究了这一新引入的参数，用于休息时间限制的动态路径问题，其中每个节点的等待时间受到限制。 在本文中，我们证明，在区间模型中，其中弧在整个时间区间内存在，即使顶点区间成员宽度等于三，寻找休息时间动态路径仍然是 NP 难的。 我们展示了针对点模型的 FPT 算法，其中弧在特定时间点存在，包括延迟为一的情况和任意正延迟的情况。 在后一种情况下，这会带来一些额外的计算成本。 显示英文摘要

摘要： 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.