论文标题
不安的时间路径参数为高于下限
Restless Temporal Path Parameterized Above Lower Bounds
论文作者
论文摘要
可及性问题是时间图中最基本的算法原始算法之一 - 在离散时间步骤中，其边缘集的图形变化。这里的一个核心问题是NP-HARD短暂的暂时性路径：给定时间图$ \ MATHCAL G $，两个不同的Vertices $ s $和$ z $，以及两个数字$δ$和$ k $，最多$ k $的$Δ$Δ$ - restless $ s $ s $ s $ - $ s $ z $？时间路径是一条路径，其边缘以时间顺序出现，如果两个连续的路径边缘出现在最多$δ$Δ$彼此之间，则时间路径为$Δ$。除其他外，此问题在神经科学和流行病学中都有应用。虽然已知短暂的不安定时间路径在计算上很难，例如，它仅在三个时间步长而w [1] - hard时，当由基础图的反馈顶点编号进行参数化时，当通过路径长度$ k $参数化时，它是固定参数可访问的。我们通过证明可以在（随机）$ 4^{k-d} | \ Mathcal g |^{o（1）} $ pime中求解的短暂不安的时间路径来改进这一点，其中$ d $是时间$ s $ s $ z $路径的最小长度。
Reachability questions are one of the most fundamental algorithmic primitives in temporal graphs -- graphs whose edge set changes over discrete time steps. A core problem here is the NP-hard Short Restless Temporal Path: given a temporal graph $\mathcal G$, two distinct vertices $s$ and $z$, and two numbers $δ$ and $k$, is there a $δ$-restless temporal $s$-$z$ path of length at most $k$? A temporal path is a path whose edges appear in chronological order and a temporal path is $δ$-restless if two consecutive path edges appear at most $δ$ time steps apart from each other. Among others, this problem has applications in neuroscience and epidemiology. While Short Restless Temporal Path is known to be computationally hard, e.g., it is NP-hard for only three time steps and W[1]-hard when parameterized by the feedback vertex number of the underlying graph, it is fixed-parameter tractable when parameterized by the path length $k$. We improve on this by showing that Short Restless Temporal Path can be solved in (randomized) $4^{k-d}|\mathcal G|^{O(1)}$ time, where $d$ is the minimum length of a temporal $s$-$z$ path.
