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 \(\zeta = L - \lambda\) between this bound and the target makespan \(\lambda\), together with the number \(k\) of agents. Our main result establishes fixed-parameter tractability for the combined parameter \(k + \zeta\). Matching lower bounds show that parameterization by \(k\) alone is W[1]-hard, and that parameterization by \(\zeta\) 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 \(\zeta\). Finally, we show that Transient Multiagent Pathfinding is unlikely to admit a polynomial kernel when parameterized by \(k + \zeta\). Together, our results provide an almost complete characterization of the parameterized complexity landscape of the problem for the considered parameters.