{"ID":22952715,"CreatedAt":"2026-09-17T02:12:05.498442134Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.18802","arxiv_id":"2609.18802","title":"Routing Multiple Agents Below the Sum of Distances","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.","short_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 parameter...","url_abs":"https://arxiv.org/abs/2609.18802","url_pdf":"https://arxiv.org/pdf/2609.18802v1","authors":"[\"Matthias Bentert\",\"Eduard Eiben\",\"Fedor V. Fomin\",\"Petr A. Golovach\"]","published":"2026-09-16T15:16:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}