论文标题
在紧密连接的有向图上，MAPF的小解决方案假设是真实的
The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True
论文作者
论文摘要
多年来，定向图（DIMAPF）上多代理探路的计算复杂性一直是一个开放的研究问题。虽然DIMAPF在某些特殊情况下已被证明是多项式的，但直到最近，已经确定该问题通常是NP-HARD。此外，已经证明，如果针对有牢固连接的有向图的简短解决方案假设正确，则DIMAPF将位于NP中。在本文中，即使在允许同步旋转时，这一假设确实是正确的。
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.
