Restless reachability problems in temporal graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913594714619904 |
|---|---|
| author | Thejaswi, Suhas Lauri, Juho Gionis, Aristides |
| author_facet | Thejaswi, Suhas Lauri, Juho Gionis, Aristides |
| contents | 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 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 other.
We present an algebraic algorithmic framework based on constrained multi\-linear sieving for solving the restless reachability problems we propose. In particular, parameterized by the length $k$ of a path sought, we show that the proposed problems can be solved in $O(2^k k m Δ)$ time and $O(n Δ)$ space, where $n$ is the number of vertices, $m$ the number of edges, and $Δ$ the maximum resting time of an input temporal graph. 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 real-world graphs. Our implementation is efficiently engineered and highly optimized. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2010_08423 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Restless reachability problems in temporal graphs Thejaswi, Suhas Lauri, Juho Gionis, Aristides Data Structures and Algorithms Distributed, Parallel, and Cluster Computing F.2.2; G.4; F.2.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 kind 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 other. We present an algebraic algorithmic framework based on constrained multi\-linear sieving for solving the restless reachability problems we propose. In particular, parameterized by the length $k$ of a path sought, we show that the proposed problems can be solved in $O(2^k k m Δ)$ time and $O(n Δ)$ space, where $n$ is the number of vertices, $m$ the number of edges, and $Δ$ the maximum resting time of an input temporal graph. 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 real-world graphs. Our implementation is efficiently engineered and highly optimized. |
| title | Restless reachability problems in temporal graphs |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing F.2.2; G.4; F.2.1 |
| url | https://arxiv.org/abs/2010.08423 |