Thejaswi Suhas, Lauri Juho, Gionis Aristides
Max Planck Institute for Software Systems, Kaiserslautern, Germany.
Helsinki, Finland.
Knowl Inf Syst. 2025;67(7):5651-5697. doi: 10.1007/s10115-025-02405-6. Epub 2025 Apr 1.
We study a family of reachability problems under waiting-time restrictions in temporal and vertex-colored temporal graphs. Given a temporal graph and a set of source vertices, we find the set of vertices that are reachable from a source via a time-respecting path, where the difference in timestamps between consecutive edges is at most a resting time. Given a vertex-colored temporal graph and a multiset query of colors, we find the set of vertices reachable from a source via a time-respecting path such that the vertex colors of the path agree with the multiset query and the difference in timestamps between consecutive edges is at most a resting time. These kinds of problems have applications in understanding the spread of a disease in a network, tracing contacts in epidemic outbreaks, finding signaling pathways in the brain network, and recommending tours for tourists, among others. We present an algebraic algorithmic framework based on constrained multilinear sieving for solving the restless reachability problems we propose. In particular, parameterized by the length of a path sought, we show that the proposed problems can be solved in time and space, where is the number of vertices, the number of edges, and the maximum resting time of an input temporal graph. The approach can be extended to extract paths and connected subgraphs in both static and temporal graphs, thus improving the work of Björklund et al. (in Proceedings of the European symposium on algorithms, 2014) and Thejaswi et al. (Big Data 8:335-362, 2020). In addition, we prove that our algorithms for the restless reachability problems in vertex-colored temporal graphs are optimal under plausible complexity-theoretic assumptions. Finally, with an open-source implementation, we demonstrate that our algorithm scales to large graphs with up to one billion temporal edges, despite the problems being NP-hard. Specifically, we present extensive experiments to evaluate our scalability claims both on synthetic and on real-world graphs. Our implementation is efficiently engineered and highly optimized. For instance, we can solve the restless reachability problem by restricting the path length to 9 in a real-world graph dataset with over 36 million directed edges in less than one hour on a commodity desktop with a 4-core Haswell CPU.
我们研究了时态图和顶点着色时态图中等待时间限制下的一系列可达性问题。给定一个时态图和一组源顶点，我们要找出通过一条尊重时间的路径从源点可达的顶点集，其中连续边的时间戳之差至多为一个静止时间。给定一个顶点着色时态图和一个颜色多重集查询，我们要找出通过一条尊重时间的路径从源点可达的顶点集，使得路径的顶点颜色与多重集查询一致，且连续边的时间戳之差至多为一个静止时间。这类问题在理解疾病在网络中的传播、追踪疫情爆发中的接触者、在脑网络中寻找信号通路以及为游客推荐旅游线路等方面都有应用。我们提出了一种基于约束多线性筛法的代数算法框架来解决我们提出的不安分可达性问题。特别地，以所求路径的长度为参数，我们证明所提出的问题可以在 时间和 空间内解决，其中 是顶点数， 是边数， 是输入时态图的最大静止时间。该方法可以扩展到在静态图和时态图中提取路径和连通子图，从而改进了比约克伦德等人（《欧洲算法研讨会论文集》，2014 年）以及特贾斯维等人（《大数据》8:335 - 362，2020 年）的工作。此外，我们证明在合理的复杂性理论假设下，我们针对顶点着色时态图中不安分可达性问题的算法是最优的。最后，通过一个开源实现，我们证明尽管这些问题是 NP 难问题，但我们的算法可以扩展到处理具有多达十亿条时态边的大型图。具体来说，我们进行了广泛的实验来评估我们关于在合成图和真实世界图上的可扩展性的断言。我们的实现经过了高效设计和高度优化。例如，在一个具有 4 核 Haswell CPU 的普通桌面上，我们可以在不到一小时的时间内，在一个具有超过 3600 万条有向边的真实世界图数据集中，通过将路径长度限制为 9 来解决不安分可达性问题。
