Tzvika Geft proves NP-hardness for multi-agent pathfinding on trees

Multi-Agent Path Finding (MAPF) is a core robotics problem where multiple agents move on a graph to reach target vertices without collisions, optimizing objectives like total distance, makespan, or flowtime. Despite years of study, the complexity of MAPF on trees—a very restricted graph class—remained open for several fundamental variants. Tzvika Geft's new paper, 'On the Hardness of Optimal Motion on Trees,' definitively closes this gap by proving NP-hardness for both labeled (distinct agents with unique targets) and 2-colored (agents interchangeable within color groups) MAPF under all three standard objectives.

The proof leverages a reduction from the Stack Rearrangement problem, itself shown NP-hard in the same work. This connection elegantly shows that hardness holds even on 'subdivided stars'—trees with a central hub and thin branches. Notably, the result resolves the classical Pebble Motion problem on trees, where a single pebble moves to an adjacent empty vertex and the goal is to minimize total moves. This problem had remained open for decades and is now proven NP-hard. For colored Pebble Motion, this is the first hardness result on any graph class, and it is tight (2 colors suffice). Geft's framework unifies and strengthens prior hardness results, revealing a fundamental tractability barrier that permeates several motion models used in robotics, warehouse logistics, and multi-robot coordination.