Interference-free Walks in Time: Temporally Disjoint Paths

Klobas, Nina; Mertzios, George B.; Molter, Hendrik; Niedermeier, Rolf; Zschoche, Philipp

doi:10.24963/ijcai.2021/563

Interference-free Walks in Time: Temporally Disjoint Paths

Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4090-4096.

https://doi.org/10.24963/ijcai.2021/563

Keywords

Agent-based and Multi-agent Systems: Multi-agent Planning
Planning and Scheduling: Planning and Scheduling
Planning and Scheduling: Scheduling

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 routes. However, it is polynomial-time 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.

Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche. 2021. Interference-free Walks in Time: Temporally Disjoint Paths. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4090–4096. https://doi.org/10.24963/ijcai.2021/563

@inproceedings{ijcai2021p563,
  title     = {Interference-free Walks in Time: Temporally Disjoint Paths},
  author    = {Klobas, Nina and Mertzios, George B. and Molter, Hendrik and Niedermeier, Rolf and Zschoche, Philipp},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4090--4096},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/563},
  url       = {https://doi.org/10.24963/ijcai.2021/563},
}

TY  - CPAPER
TI  - Interference-free Walks in Time: Temporally Disjoint Paths
AU  - Klobas, Nina
AU  - Mertzios, George B.
AU  - Molter, Hendrik
AU  - Niedermeier, Rolf
AU  - Zschoche, Philipp
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4090
EP  - 4096
DO  - 10.24963/ijcai.2021/563
UR  - https://doi.org/10.24963/ijcai.2021/563
ER  -