  On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists
in finding paths for multiple agents, avoiding collisions. Finding the
minimum-length solution is known to be NP-hard, and computation times grows
exponentially with the number of agents. However, in industrial applications,
it is important to find feasible, suboptimal solutions, in a time that grows
polynomially with the number of agents. Such algorithms exist for undirected
and biconnected directed graphs. Our main contribution is to generalize these
algorithms to the more general case of strongly connected directed graphs. In
particular, given a MAPF problem with at least two holes, we present an
algorithm that checks the problem feasibility in linear time with respect to
the number of nodes, and provides a feasible solution in polynomial time.
