Zig-Zag Numberlink is NP-Complete

Aaron Adcock, Erik D. Demaine, Martin L. Demaine +4

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 ha…