Zig-Zag Numberlink is NP-Complete
Zig-Zag Numberlink is NP-Complete
复制标题
DOI：
10.2197/ipsjjip.23.239
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
Aaron B. Adcock;E. Demaine;M. Demaine;Michael P. O’Brien;F. Reidl;Fernando Sánchez Villaamil;Blair D. Sullivan
中科院分区：
文献类型：
--
作者：
Aaron B. Adcock;E. Demaine;M. Demaine;Michael P. O’Brien;F. Reidl;Fernando Sánchez Villaamil;Blair D. Sullivan
$m \times n$ 网格中的 $t$ 终端对何时可以通过覆盖网格所有顶点的 $t$ 顶点不相交路径连接？我们证明这个问题是NP完全问题。我们的硬度结果可以与之前的两个 NP 硬度证明进行比较：林奇 1975 年的证明，没有“覆盖所有顶点”约束，以及 Kotsuma 和 Takenaga 的 2010 年证明，当时路径被限制为在同伦类中具有尽可能少的角点。后一个限制是著名的 Nikoli 难题 \emph{Numberlink} 的常见形式；我们的问题是 Numberlink 的另一种常见形式，有时称为 \emph{Zig-Zag Numberlink} 并由智能手机应用程序 \emph{Flow Free} 普及。
When can $t$ terminal pairs in an $m \times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the ``cover all vertices'' constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle \emph{Numberlink}; our problem is another common form of Numberlink, sometimes called \emph{Zig-Zag Numberlink} and popularized by the smartphone app \emph{Flow Free}.