# On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2019.

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

- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True](https://mlsanity.com/paper/2210.04590/) (2022)
- [Multi-Agent Path Finding via Tree LSTM](https://mlsanity.com/paper/2210.12933/) (2022)
- [Efficient Constraint Generation for Stochastic Shortest Path Problems](https://mlsanity.com/paper/2604.01855/) (2026)
- [Efficient Constraint Generation for Stochastic Shortest Path Problems](https://mlsanity.com/paper/2401.14636/) (2024)
- [Multi-Agent Path Finding For Large Agents Is Intractable](https://mlsanity.com/paper/2505.10387/) (2025)
- [Budget Allocation Policies for Real-Time Multi-Agent Path Finding](https://mlsanity.com/paper/2507.16874/) (2025)

## Abstract (arXiv)

The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs is solvable in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven.