论文标题
Menger的时间道路定理（不走路）
Menger's Theorem for Temporal Paths (Not Walks)
论文作者
论文摘要
（定向）的时间图是（有向）图，其边缘仅在其寿命$τ$的特定时间内可用。时间步行是相邻边缘的序列，其出现时间严格增加或不折叠（此处称为非图案），具体取决于场景。路径是不允许重复顶点重复的时间步行。临时顶点是一对$（u，i）$，其中$ u $是顶点，而$ i \ in [τ] $ a timestep。在本文中，我们关注的问题：（i）从单个来源$ s $到单个目标$ t $的$ k $路径至少有$ k $路径，其中没有两个内部在时间顶点上相交？ （ii）最多有$ h $ terimal的顶点，其删除将$ s $与$ t $断开连接？令$ k^*$为最大值$ k $，对（i）的答案是肯定的，然后让$ h^*$为最小值$ h $（ii）的答案是肯定的。在静态图中，Menger的定理是$ k^*$和$ h^*$相同的，这是有效解决（i）和（ii）的关键属性。在时间表中，已经研究了这种平等，仅着眼于截然不同的步行而不是不相交的路径。在这种情况下，我们证明$ k^*$等于$ h^*$，并且仅当$ k^*$为1。我们表明这意味着（i）的二分法，当时可以在$ k \ le 2 $和np-complete时$ k \ ge ge 3 $ np-complete时可溶解。最后，我们给出硬度结果和（ii）的XP算法。
A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its lifetime $τ$. Temporal walks are sequences of adjacent edges whose appearing times are either strictly increasing or non-decreasing (here called non-strict), depending on the scenario. Paths are temporal walks where no vertex repetition is allowed. A temporal vertex is a pair $(u,i)$ where $u$ is a vertex and $i\in[τ]$ a timestep. In this paper we focus on the questions: (i) are there at least $k$ paths from a single source $s$ to a single target $t$, no two of which internally intersect on a temporal vertex? (ii) are there at most $h$ temporal vertices whose removal disconnects $s$ from $t$? Let $k^*$ be the maximum value $k$ for which the answer to (i) is YES, and let $h^*$ be the minimum value $h$ for which the answer to (ii) is YES. In static graphs, $k^*$ and $h^*$ are equal by Menger's Theorem and this is a crucial property to solve efficiently both (i) and (ii). In temporal graphs such equality has been investigated only focusing on disjoint walks rather than disjoint paths. In this context, we prove that $k^*$ is equal to $h^*$ if and only if $k^*$ is 1. We show that this implies a dichotomy for (i), which turns out to be polynomial-time solvable when $k \le 2$, and NP-complete for $k \ge 3$. Finally, we give hardness results and an XP algorithm for (ii).
