Skip to main content

Research Repository

Advanced Search

Interference-free walks in time: temporally disjoint paths

Klobas, N.; Mertzios, G.B.; Molter, H.; Niedermeier, R.; Zschoche, P.

Interference-free walks in time: temporally disjoint paths Thumbnail


Authors

Nina Klobas nina.klobas@durham.ac.uk
PGR Student Doctor of Philosophy

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





You might also like



Downloadable Citations