# Routing Multiple Agents Below the Sum of Distances

Preprint · Matthias Bentert, Eduard Eiben, Fedor V. Fomin, Petr A. Golovach

- Archive id: arxiv:2609.18802
- Published: 2026-09-16
- arXiv: https://arxiv.org/abs/2609.18802
- Source URL: https://arxiv.org/abs/2609.18802
- PDF: https://arxiv.org/pdf/2609.18802
- Provenance: arxiv

## Abstract

We study Transient Multiagent Pathfinding, a variant of the classical Multi-Agent Pathfinding problem in which a set of agents must be routed without collisions from designated start vertices to designated destination vertices in a graph. We analyze the problem within the above-and-below-guarantee paradigm of parameterized complexity. In particular, we consider the natural upper bound \\(L\\), given by the sum of the shortest-path distances between pairs of agents' terminals (corresponding to sequential routing of the agents). The parameterization is given by the gap \\(ζ= L - λ\\) between this bound and the target makespan \\(λ\\), together with the number \\(k\\) of agents. Our main result establishes fixed-parameter tractability for the combined parameter \\(k + ζ\\). Matching lower bounds show that parameterization by \\(k\\) alone is W\[1\]-hard, and that parameterization by \\(ζ\\) alone is W\[1\]-hard when terminals are not required to be distinct. On the positive side, if all terminals are distinct, the problem becomes fixed-parameter tractable when parameterized solely by \\(ζ\\). Finally, we show that Transient Multiagent Pathfinding is unlikely to admit a polynomial kernel when parameterized by \\(k + ζ\\). Together, our results provide an almost complete characterization of the parameterized complexity landscape of the problem for the considered parameters.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.