Routing Multiple Agents Below the Sum of Distances: A Parameterized Complexity Characterization of Transient Multiagent Pathfinding

Main result: Transient Multiagent Pathfinding is fixed-parameter tractable with respect to the combined parameter k+ζ, solvable in 2^{O(k²ζ)}·n^{O(1)} time. Prior parameterized work on this problem focused on natural parameters such as the number of agents, the makespan, or structural parameters like treewidth; this paper is the first to adopt the above-and-below-guarantee paradigm, parameterizing by the improvement ζ over the sequential-routing upper bound L together with k. The proof rests on a sequence of structural lemmas: a 2^{O(kλ)}·n^{O(1)} color-coding algorithm (Lemma 7) and an (kn)^{O(k)} XP algorithm (Lemma 6), followed by sufficient conditions in Lemmas 9–16 that reduce the general case to instances where shortest-path lengths are O(ζ), with a final case analysis over terminal distances.

Lower bounds: the problem is W[1]-hard parameterized by k alone (even on subcubic graphs), W[1]-hard parameterized by ζ alone when terminals need not be distinct, and admits no polynomial kernel for k+ζ unless coNP⊆NP/poly. These results complement the main theorem, showing that the combined parameterization k+ζ cannot be weakened, and together they yield an almost complete characterization of the problem's parameterized complexity for the considered parameters. W[1]-hardness follows from parameterized reductions from Layered Vertex-Disjoint Shortest Paths (Theorems 23 and 25, Corollary 24); the kernel lower bound follows from a polynomial parameter transformation from the same problem (Theorem 26).

Positive special case: when all terminals are pairwise distinct, the upper bound improves to L*_{R,G}=Σdist(si,ti)−⌊(k−1)/2⌋, and the problem becomes fixed-parameter tractable in ζ alone, solvable in 2^{O(ζ³)}·n^{O(1)} time. This identifies a natural subclass in which the single parameter ζ suffices for fixed-parameter tractability, in contrast to the W[1]-hardness for ζ alone when terminals may repeat. Key Lemma 21 shows that among any three agents with distinct terminals, two can be routed without conflicts within makespan dist(si,ti)+dist(sj,tj)−1; Lemma 22 derives the improved bound L*_{R,G}; Theorem 2 combines this with the main theorem to obtain the algorithm.

Basic structural facts: sequential routing yields the tight upper bound L=1+Σdist(si,ti), and the problem reduces to Disjoint Paths on a time-expansion graph. The upper bound was previously an intuitive strategy; this paper formalizes it, proves its tightness (via a path graph with swapped endpoints), and gives a construction encoding the no-collision constraints into the time-expansion graph G*_λ. Lemma 3 establishes the bound and schedule properties; Observations 4 and 5 establish equivalence with vertex-disjoint paths in the time-expansion graph, yielding both the XP and color-coding algorithms.

The results apply to the model in which agents disappear immediately upon reaching their destinations, may move or wait at each step, and no two agents may occupy the same vertex or traverse the same edge at the same time step; the algorithms are parameterized by the number of agents k and the improvement ζ over the upper bound L, so they are most useful when ζ is small and k is manageable. The distinct-terminals special case improves the bound to L*_{R,G}, making the single parameter ζ sufficient for a fixed-parameter algorithm. These results characterize complexity boundaries of solvability rather than schedule quality in concrete systems.

The paper lists several open questions: whether the inequality λ≤2·max_i dist(si,ti)+k holds in general for the minimum makespan remains neither proved nor disproved; whether the problem parameterized solely by ζ is in XP or para-NP-hard is unresolved; and whether the problem is fixed-parameter tractable in k on planar graphs or planar grids is also open. In addition, this is a theoretical analysis without experimental evaluation, so performance on real systems would need separate validation.