Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Interference-free walks in time: temporally disjoint paths

Klobas, N. and Mertzios, G.B. and Molter, H. and Niedermeier, R. and Zschoche, P. (2021) 'Interference-free walks in time: temporally disjoint paths.', 30th International Joint Conference on Artificial Intelligence (IJCAI-21) Montreal / Virtual, 21 Aug - 26 Aug 2021.

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.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
(287Kb)
Status:Peer-reviewed
Publisher Web site:https://ijcai-21.org/
Date accepted:20 May 2021
Date deposited:14 June 2021
Date of first online publication:2021
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar