Restless reachability problems in temporal graphs

Area of Science:

• Graph Theory and Algorithms
• Network Science
• Computational Complexity

Background:

• Temporal graphs model dynamic networks where connections change over time.
• Reachability problems with waiting-time restrictions are crucial for analyzing real-world processes like disease spread and information diffusion.
• Existing methods struggle with the complexity of temporal graphs and vertex coloring constraints.

Purpose of the Study:

• To develop an efficient algorithmic framework for restless reachability problems in temporal and vertex-colored temporal graphs.
• To analyze the time and space complexity of these problems, particularly concerning path length and resting time.
• To provide an optimal and scalable solution for practical applications, including disease spread and network analysis.

Main Methods:

• An algebraic algorithmic framework based on constrained multilinear sieving is proposed.
• Parameterized complexity analysis is used, focusing on path length (k) and maximum resting time (Δ).
• An open-source implementation is developed and rigorously tested on synthetic and real-world datasets.

Main Results:

• The proposed problems are solvable in O(2^k * k * m * Δ) time and O(n * Δ) space, parameterized by path length k.
• Algorithms for vertex-colored temporal graphs are proven to be optimal under plausible complexity assumptions.
• The implementation demonstrates scalability to graphs with up to one billion temporal edges, solving complex problems efficiently.

Conclusions:

• The developed framework provides a significant advancement in solving restless reachability problems in temporal networks.
• The algorithms are efficient, scalable, and optimal for vertex-colored temporal graphs, offering practical solutions.
• The open-source implementation facilitates further research and application in diverse fields like epidemiology and network analysis.