A temporal (directed) graph is a (directed) graph whose edge availability varies over time, and temporal walks are sequences of adjacent edges respecting these availabilities. A third component of this scenario imposes time constraints on the vertices, known as “waiting time constraints.” Drawing a parallel with a transportation network, these constraints can be envisioned as the minimum and maximum time a person would need or be willing to stay at the same location. It is known that computing a temporal walk between a pair of vertices under waiting time constraints can be achieved in polynomial time, even when optimizing certain criteria. In this article, we extend these investigations to the problem of finding k temporal walks such that no two distinct walks overlap in time. Given a multiset \(\{(s_1, z_1), \ldots , (s_k, z_k)\}\) of pairs of vertices of a temporal graph \(\mathcal {G}\) , we consider the problem of finding a set of pairwise temporally disjoint walks \(P_1, \ldots , P_k\) such that each \(P_i\) is a temporal walk from \(s_i\) to \(z_i\) . Under a given set of waiting time constraints, when \(s_i = s\) and \(z_i = z\) for all \(i \in [k]\) we show that determining the existence of such walks is \(\textsf {W}[1]\) -hard when parameterized by k, and that it is \(\textsf {NP}\) -complete to decide the existence of a separator (i.e., a set of vertex occurrences in time intersecting all such walks) of size at most h. In the more general case, when the vertices \(s_i\) and \(z_i\) are allowed to be disjoint, we show that the walks can be found in \(\textsf {XP}\) time parameterized by k when each walk has to wait at least \(\omega _L(u) \ge 1\) units of time on each occurrence of each vertex u used by the walk, and that the separator can be found in \(\textsf {XP}\) time with parameter h.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Disjoint Temporal Walks Under Waiting Time Constraints

  • Allen Ibiapina,
  • Raul Lopes,
  • Andrea Marino,
  • Ana Silva

摘要

A temporal (directed) graph is a (directed) graph whose edge availability varies over time, and temporal walks are sequences of adjacent edges respecting these availabilities. A third component of this scenario imposes time constraints on the vertices, known as “waiting time constraints.” Drawing a parallel with a transportation network, these constraints can be envisioned as the minimum and maximum time a person would need or be willing to stay at the same location. It is known that computing a temporal walk between a pair of vertices under waiting time constraints can be achieved in polynomial time, even when optimizing certain criteria. In this article, we extend these investigations to the problem of finding k temporal walks such that no two distinct walks overlap in time. Given a multiset \(\{(s_1, z_1), \ldots , (s_k, z_k)\}\) of pairs of vertices of a temporal graph \(\mathcal {G}\) , we consider the problem of finding a set of pairwise temporally disjoint walks \(P_1, \ldots , P_k\) such that each \(P_i\) is a temporal walk from \(s_i\) to \(z_i\) . Under a given set of waiting time constraints, when \(s_i = s\) and \(z_i = z\) for all \(i \in [k]\) we show that determining the existence of such walks is \(\textsf {W}[1]\) -hard when parameterized by k, and that it is \(\textsf {NP}\) -complete to decide the existence of a separator (i.e., a set of vertex occurrences in time intersecting all such walks) of size at most h. In the more general case, when the vertices \(s_i\) and \(z_i\) are allowed to be disjoint, we show that the walks can be found in \(\textsf {XP}\) time parameterized by k when each walk has to wait at least \(\omega _L(u) \ge 1\) units of time on each occurrence of each vertex u used by the walk, and that the separator can be found in \(\textsf {XP}\) time with parameter h.