# The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 45 references that are in the map.
- First posted on arXiv 10 Oct 2022.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs](https://mlsanity.com/paper/1911.04871/) (2019)
- [Refined Hardness of Distance-Optimal Multi-Agent Path Finding](https://mlsanity.com/paper/2203.07416/) (2022)
- [AI Buzzwords Explained: Multi-Agent Path Finding (MAPF)](https://mlsanity.com/paper/1710.03774/) (2017)
- [Multi-Agent Path Finding on Strongly Connected Digraphs: feasibility and solution algorithms](https://mlsanity.com/paper/2209.04286/) (2022)

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

- [Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time](https://mlsanity.com/paper/2512.22171/) (2025)

## Abstract (arXiv)

The determination of the computational complexity of multi-agent pathfinding on directed graphs (diMAPF) has been an open research problem for many years. While diMAPF has been shown to be polynomial for some special cases, only recently, it has been established that the problem is NP-hard in general. Further, it has been proved that diMAPF will be in NP if the short solution hypothesis for strongly connected directed graphs is correct. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.