Interference-free Walks in Time: Temporally Disjoint Paths
Authors: Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Nina Klobas1 , George B. Mertzios1 , Hendrik Molter2 , Rolf Niedermeier3 and Philipp Zschoche3 1Department of Computer Science, Durham University, UK 2Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Israel 3Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Germany |
| Pseudocode | No | The paper describes algorithmic approaches and dynamic programming formulations in text, but it does not include any explicitly labeled 'Pseudocode' or 'Algorithm' blocks or figures. |
| Open Source Code | No | The paper does not contain any statement about making its source code available or provide a link to a code repository. |
| Open Datasets | No | This paper is theoretical and does not use or reference any datasets for training or evaluation. |
| Dataset Splits | No | This paper is theoretical and does not describe experimental setups with dataset splits. |
| Hardware Specification | No | This paper is theoretical and does not report on experiments requiring hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not report on experiments requiring specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |