Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top