  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.
