# Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology

arXiv: https://arxiv.org/abs/2312.09646 · HTML: https://mlsanity.com/paper/2312.09646/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 15 Dec 2023.

## Builds on (most cited first, 8 of 8)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [An Improved Parameterized Algorithm for Treewidth](https://mlsanity.com/paper/2211.07154/) (2022)
- [The Parameterized Complexity of Coordinated Motion Planning](https://mlsanity.com/paper/2312.07144/) (2023)
- [Shrub-depth: Capturing Height of Dense Graphs](https://mlsanity.com/paper/1707.00359/) (2017)
- [Hardness of Token Swapping on Trees](https://mlsanity.com/paper/2103.06707/) (2021)

## Built on by (most cited first, 4 of 4)

- [Solving Multiagent Path Finding on Highly Centralized Networks](https://mlsanity.com/paper/2412.09433/) (2024)
- [Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures](https://mlsanity.com/paper/2412.08556/) (2024)
- [When Agents Break Down in Multiagent Path Finding](https://mlsanity.com/paper/2508.03777/) (2025)
- [Integrated packing, placement, scheduling, and routing of personalized production: a pharmaceutical Industry 4.0 use-case with a planar transport system](https://mlsanity.com/paper/2604.21029/) (2026)

## Abstract (arXiv)

In the Multiagent Path Finding problem (MAPF for short), we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule ℓ, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our fixed-parameter tractability results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespanℓ are fixed constants. On the positive side, we show an FPT algorithm for k+ℓ. As we delve further, the structure of~G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph~G. The MAPF problem is W[1]-hard for cliquewidth of G plus ℓ while it is FPT for treewidth of G plus ℓ.