Preprint
Abstract
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}.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Yosenabe is NP-completeJournal of Information Processing, 2014
- A SURVEY OF NP-COMPLETE PUZZLESICGA Journal: The Journal of the Computer Games Community, 2008
- Hamilton Paths in Grid GraphsSIAM Journal on Computing, 1982
- The equivalence of theorem proving and the interconnection problemACM SIGDA Newsletter, 1975