Nina Klobas nina.klobas@durham.ac.uk
PGR Student Doctor of Philosophy
Interference-free walks in time: temporally disjoint paths
Klobas, N.; Mertzios, G.B.; Molter, H.; Niedermeier, R.; Zschoche, P.
Authors
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
H. Molter
R. Niedermeier
P. Zschoche
Abstract
We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never use the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. On the one extreme, we show that on general graphs the problem is computationally hard. The “walk version” is W[1]-hard when parameterized by the number of walks. However, it is polynomialtime solvable for any constant number of walks. The “path version” remains NP-hard even if we want to find only two temporally disjoint paths. On the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counterintuitively, we find NP-hardness in general but also identify natural tractable cases.
Citation
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021). Interference-free walks in time: temporally disjoint paths. . https://doi.org/10.24963/ijcai.2021/563
Conference Name | 30th International Joint Conference on Artificial Intelligence (IJCAI-21) |
---|---|
Conference Location | Montreal, Quebec |
Start Date | Aug 21, 2021 |
End Date | Aug 26, 2021 |
Acceptance Date | May 20, 2021 |
Publication Date | 2021 |
Deposit Date | Jun 13, 2021 |
Publicly Available Date | Jun 14, 2021 |
Pages | 4090-4096 |
DOI | https://doi.org/10.24963/ijcai.2021/563 |
Related Public URLs | https://arxiv.org/abs/2105.08335 |
Files
Accepted Conference Proceeding
(293 Kb)
PDF
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search