Interference-free Walks in Time: Temporally Disjoint Paths

Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Philipp ZschocheIJCAI 2021 · DOI

TL;DR

This paper introduces and analyzes the computational complexity of finding "temporally disjoint" paths and walks in temporal graphs, where edges change over time. They discover a surprising difference: finding temporally disjoint walks is computationally easier than finding paths, especially when the underlying graph structure is restricted.

What Problem Does This Paper Address?

The paper tackles the problem of finding paths or walks in graphs where edges are not static but appear and disappear over discrete time steps. This "temporal graph" model is motivated by real-world applications like multi-agent pathfinding in robotics, traffic routing, and communication networks, where dynamic availability of routes is crucial. The core challenge is to find multiple paths/walks that do not "interfere" – meaning they don't occupy the same vertex at the same point in time. This is a temporal generalization of the well-studied vertex-disjoint paths problem in static graphs. The authors investigate this problem in two extreme scenarios: unrestricted underlying graphs and underlying graphs that are simple paths.

Methods

The authors employ a combination of theoretical computer science techniques, primarily focusing on computational complexity analysis. They use reductions from known NP-complete problems (like EXACT (3,4)-SAT) to prove NP-hardness for certain variants of their problem. They also leverage concepts from parameterized complexity, defining and analyzing classes like W[1]-hard and XP, to understand how the problem's difficulty scales with parameters like the number of paths/walks. For specific tractable cases, they develop dynamic programming algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Walks vs. Paths Distinction: The most striking insight is the significant computational difference between finding temporally disjoint walks and paths. While finding disjoint paths remains hard even for a small number of pairs, finding disjoint walks can be much more tractable, especially in certain scenarios.
  • Temporal Graphs Add Complexity: The temporal dimension introduces new challenges. Even on simple structures like paths, finding temporally disjoint paths can be NP-hard, a contrast to some static graph problems.
  • Underlying Graph Structure Matters: The complexity drastically changes based on the underlying static graph structure. Unrestricted graphs and path graphs exhibit different hardness results.
  • Counterintuitive Tractability on Paths: Counterintuitively, when the underlying graph is a path, the problem of finding temporally disjoint paths becomes fixed-parameter tractable (FPT) with respect to the number of paths, a much better result than the general case.

Key Results

  • Unrestricted Graphs:
    • TEMPORALLY DISJOINT PATHS is NP-hard even for two source-sink pairs and a small number of time steps (T=3).
  • TEMPORALLY DISJOINT WALKS is W[1]-hard when parameterized by the number of walks, but polynomial-time solvable for a constant number of walks (XP).
  • Temporal Line (Path) Underlying Graph:
    • TEMPORALLY DISJOINT (PATHS/WALKS) remains NP-hard in general.
  • TEMPORALLY DISJOINT PATHS is fixed-parameter tractable (FPT) with respect to the number of source-sink pairs.
  • A polynomial-time algorithm exists for finding temporally disjoint paths/walks when the underlying graph is a path and all source-sink pairs are between the two endpoints of the path.

Limitations and Future Work

  • Walks on Temporal Trees: The paper leaves open whether TEMPORALLY DISJOINT WALKS is FPT when parameterized by the number of walks on temporal trees. They suspect it's more complicated than the path version due to the possibility of walks not being simple paths.
  • General Temporal Graphs: The paper focuses on two extreme cases (unrestricted and path graphs). Analyzing intermediate graph structures (like trees) for paths and walks would be a natural extension.
  • Practical Algorithms: While theoretical complexity is analyzed, the paper doesn't present practical implementations or empirical evaluations of the proposed algorithms.

Summary updated

BibTeX
@inproceedings{klobas2021interference,
  author = {Nina Klobas and George B. Mertzios and Hendrik Molter and Rolf Niedermeier and Philipp Zschoche},
  title = {{Interference-free Walks in Time: Temporally Disjoint Paths}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/563},
}
Figure