15
$\begingroup$

A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $n \times n$ grid graph such that each vertex is in at most one pair. A solution to such a puzzle is a set of undirected paths in the graph such that each vertex is in exactly one path and each path's set of ends is one of the puzzle's pairs of vertices. This image is an example of a Flow Free puzzle, and this image is an example of a solution to a different Flow Free puzzle.

Is the problem "Does there exist a solution to this Flow Free puzzle?" NP-hard? Does it matter whether $n$ is given in unary or binary?

$\endgroup$
  • $\begingroup$ Certainly the tricky constraint is covering all of the squares; otherwise, the problem would be solvable by a polynomial-time algorithm for the vertex-disjoint Menger problem. $\endgroup$ – David Eisenstat Oct 15 '14 at 4:51
5
$\begingroup$

In the terminology of Nikoli Puzzles this is known as "Nanbarinku" or "Numberlink". The description does not always explicitly mention all squares must be covered, but this is indeed the case in all solutions I checked.

According to Wikipedia Numberlink the problem is NP complete, with reference: Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), NP-Completeness and Enumeration of Number Link Puzzle, IEICE technical report. Theoretical foundations of Computing 109 (465): 1–7

I did not check the fine print.

Added. Following a comment from domotorp, Numberlink usually has an additional constraint. Indeed, quoting from Adcock etal:

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.

Adcock et al. Zig-Zag Numberlink is NP-Complete, Journal of Information Processing 23 (2015) 239-245, doi:10.2197/ipsjjip.23.239

$\endgroup$
  • $\begingroup$ This has an additional restriction, for the problem of the OP, see doi.org/10.2197/ipsjjip.23.239. $\endgroup$ – domotorp Dec 13 '16 at 12:16
  • $\begingroup$ @domotorp Thanks! I have copied your information to the original answer. $\endgroup$ – Hendrik Jan Dec 13 '16 at 16:01
  • $\begingroup$ It is interesting that graph planarity with fixed coordinates is in P, but adding grid space makes it NP-hard. Even for bipartite graph. $\endgroup$ – rus9384 Jan 17 '18 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy