The authors introduce the temporal variants of multi-agent path finding (MAPF) for temporal paths and temporal walks.
<aside> 💡
Definition. $\textsf{Temporally Disjoint Paths}$ and $\textsf{Temporally Disjoint Walks}$
Input: A temporal graph $\mathcal{G}=(V,E,\lambda)$ and a multiset of source–sink pairs $S=\{(s_1, t_1), \ldots, (s_k, t_k)\}\subseteq V\times V$.
Goal: Route each agent from $s_i$ to $t_i$ via a temporal journey such that no two agents:
This models a temporal movement, where each agent can use at most one edge per time step and must not revisit vertices.
</aside>
| Result | Technique |
|---|---|
| Temporally Disjoint Paths is paraNP-hard by $\lvert S\rvert$ and also by $\tau$ | Reduction from $\textsf{Exact } (3,4)\textsf{-SAT}$ |
| Temporally Disjoint Walks is W[1]-hard by $\lvert S\rvert$ even in simple graphs | Reduction from $\textsf{Disjoint Paths on DAGs}$ |
| Temporally Disjoint Walks is XP by $\lvert S\rvert$ | Streaming algorithm (DP over time $t\in\{1,\dots,\tau\}$) |
| Temporally Disjoint Paths is NP-hard on path footprint | Reduction from $\textsf{Multicolored Independent Set on Unit Interval Graphs}$ |
| Temporally Disjoint Walks is NP-hard on path footprint | Reduction from $\textsf{Multicolored Independent Set on Unit Interval Graphs}$ |
| Temporally Disjoint Paths is FPT by $\lvert S\rvert$ on tree footprint | Structural observation: exactly one static path between each source-sink pair — intersections between each pair must be traversed consecutively — enumerate all permutations |