<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>
Their problem definition:
| Result | Technique |
|---|---|
| Temporally Disjoint Paths is W[1]-hard by $\lvert S\rvert$ + vertex cover number | Reduction from $\textsf{Multicolored Clique}$ |
| Temporally Disjoint Paths is FPT by $\lvert S\rvert$ + feedback edge number | Structural observation: the number of paths in the footprint between any source-sink pair is bounded by its feedback edge number |
| The same holds for the number of intersection so any two paths. Hence, the total number of intersections is bounded by the feedback edge set number and the number of source-sink pairs. For each intersection, consider all possibilities in which order it is traversed by the temporal paths. | |
| Temporally Disjoint Paths is W[1]-hard by $\lvert V\rvert$ even on stars | Reduction from $\textsf{Unary Bin Packing}$ |
| Temporally Disjoint Walks is W[1]-hard by $\lvert V\rvert$ even on stars | Reduction from $\textsf{Unary Bin Packing}$ |
| Temporally Disjoint Walks is W[1]-hard by $\lvert S\rvert$ even on stars | Reduction from $\textsf{Multicolored Clique}$ |
| Temporally Disjoint Walks is FPT by $\lvert S\rvert$ on path footprint | Structural observation: the number of times a temporal walk in a solution $S$ changes its direction is upper-bounded by a function of $\lvert S\rvert$. Furthermore, the direction changes always occur in “regions” (whose size is upper-bounded by a function of $\lvert S\rvert$) “around” the sources and sinks in $S$. |
| This allows iteration over all possibilities in which direction, how often, and in which order the temporal walks connecting the source-sink pairs move through the regions around the source and sink vertices in $S$. Given such a possibility, check whether there exist temporally disjoint walks that realize this behavior. |
Reduction from Multicolored Clique with bounded vertex cover number
Reduction from Unary Bin Packing on stars
Reduction from Multicolored Clique on stars