Back to Search Start Over

Zig-Zag Numberlink is NP-Complete

Authors :
Adcock, Aaron
Demaine, Erik D.
Demaine, Martin L.
O'Brien, Michael P.
Reidl, Felix
Villaamil, Fernando Sánchez
Sullivan, Blair D.
Publication Year :
2014

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}.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1410.5845
Document Type :
Working Paper