Name
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}. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.2197/ipsjjip.23.239 | Journal of Information Processing |
Keywords | DocType | Volume |
np hard,discrete mathematics,games | Journal | 23 |
Issue | Citations | PageRank |
3 | 3 | 0.47 |
References | Authors | |
4 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aaron B. Adcock | 1 | 43 | 2.78 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Martin L. Demaine | 3 | 592 | 84.37 |
| Michael P. O'Brien | 4 | 3 | 0.81 |
| Felix Reidl | 5 | 99 | 12.36 |
| Fernando Sanchez Villaamil | 6 | 50 | 5.97 |
| Blair D. Sullivan | 7 | 102 | 13.93 |