We study a family of temporal reachability problems under waiting-time restrictions . In particular, 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, and such that the  difference in timestamps between consecutive edges is at most a resting time. This kind of problems have several interesting applications in understanding the spread of a disease in a network, tracing contacts in epidemic outbreaks, and finding signaling pathways in the brain network  . We present an algebraic algorithm based on constrained multilinear sieving for solving the restless reachability problems we propose. With an open-source implementation  we demonstrate that the algorithm can scale to large temporal graphs with tens of millions of edges, despite the problem being NP-hard. The 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 4-core Haswell desktop .
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 kind of problems have several 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 . 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 k sought, we show the problems can be solved in O(2^k k m \Delta) time and O(n \tau) space, where n is the number of vertices, m the number of edges, \Delta the maximum resting time and \tau the maximum timestamp of an input temporal graph. In addition, we prove that the algorithms presented 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 real-world graphs .
D
temporal
R
. In particular, given
in temporal and vertex-colored temporal graphs. Given
R
and
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
A
vertex colors of the path agree with the multiset query and the
R
This
These
D
interesting
D
and
A
, and recommending tours for tourists
R
algorithm
algorithmic framework
R
With an
In particular, parameterized by the length of a path k sought, we show the problems can be solved in O(2^k k m \Delta) time and O(n \tau) space, where n is the number of vertices, m the number of edges, \Delta the maximum resting time and \tau the maximum timestamp of an input temporal graph. In addition, we prove that the algorithms presented for the restless reachability problems in vertex-colored temporal graphs are optimal under plausible complexity-theoretic assumptions. Finally, with an
A
,
R
the algorithm can scale to large temporal graphs with tens of millions of
our algorithm scales to large graphs with up to one billion temporal
R
problem
problems
R
The 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
Specifically, we present extensive experiments to evaluate our scalability claims both on synthetic and
R
graph dataset with over 36 million directed edges in less than one hour on a 4-core Haswell desktop
graphs