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 visit 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 counter-intuitively, we find NP-hardness in general but also identify natural tractable cases.

Citation

Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2022). Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37, Article 1. https://doi.org/10.1007/s10458-022-09583-5

Journal Article Type Article
Acceptance Date Sep 22, 2022
Online Publication Date Oct 21, 2022
Publication Date 2022
Deposit Date Sep 27, 2022
Publicly Available Date Oct 22, 2023
Journal Autonomous Agents and Multi-Agent Systems
Print ISSN 1387-2532
Electronic ISSN 1573-7454
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 37
Article Number 1
DOI https://doi.org/10.1007/s10458-022-09583-5
Public URL https://durham-repository.worktribe.com/output/1190647

Files

Accepted Journal Article (489 Kb)
PDF

Copyright Statement
This version of the article has been accepted for publication, after peer review and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s10458-022-09583-5





You might also like



Downloadable Citations