Tree-MAPF: On the Complexity of Optimizing Multi Agent Path Finding on Tree Graphs

Abstract

In its general form, Multi-Agent Path Finding (MAPF) is well known to be NP-hard for various optimization objectives. But determining the complexity boundary for restricted topologies remains a key theoretical challenge. This paper investigates the complexity of MAPF on tree topologies. While recent work has established that minimizing Makespan on trees is NP-hard, the complexity of other standard metrics has remained an open question. We prove that, even on trees, optimizing Fuel (total traveled distance) and the Sum of Costs each remain NP-hard, closing a significant theoretical gap. Conversely, we identify a polynomial-time solvable case: restricting the agents to their individual shortest paths and determining if a feasible solution exists by only adding wait actions, thus maintaining the optimal Fuel cost.