7
$\begingroup$

Playing more Flow Free, I think I've realized why I'm so amazingly brilliant at this game:

The objective is to connect all pairs while covering the entire board, but in every puzzle there is always a unique solution connecting all pairs (even without the board-filling constraint).

So in a mathematical language, we are given $t$ pairs of vertices in an $n\times n$ grid, with the promise that there is only one collection of vertex disjoint paths that connects each pair, and furthermore, this unique collection covers the entire grid.

What is the complexity of this problem?

Without the promise, the problem becomes NP-hard, here is the related question with many links. (Note that the reduction in the above paper does not work for our promise version).

Update: I've realized that in the Hexagonal grid version game that I'm playing a unique solution practically (!) implies that the whole board is covered, so it's not really a big difference.

$\endgroup$
  • 1
    $\begingroup$ (Note that instances from the site I play on do not all satisfy that promise. ​ In particular, Easy Level #2 doesn't satisfy that promise.) ​ ​ ​ ​ $\endgroup$ – user6973 Jan 9 '17 at 9:36
  • $\begingroup$ Like UNAMBIGUOUS-SAT it is contained in UP and probably, applying the same technique used in the Valiant–Vazirani theorem, it could be proven that it remains a computational hard problem. $\endgroup$ – Marzio De Biasi Jan 9 '17 at 10:11
  • $\begingroup$ @Marzio There is a significant difference here - we promise something stronger than that there is only one solution to the problem, we also say that there is only one solution to a less restrictive problem. $\endgroup$ – domotorp Jan 9 '17 at 10:30
  • 1
    $\begingroup$ @MarzioDeBiasi : ​ The "less restrictive problem" is "collection of vertex disjoint paths that connects each pair". ​ ​ ​ ​ $\endgroup$ – user6973 Jan 9 '17 at 12:31
  • 1
    $\begingroup$ @Saeed: I really don't think this helps much, but if you have a solution, you're welcome to post it as an answer. $\endgroup$ – domotorp Jan 9 '17 at 19:32

Your Answer

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

Browse other questions tagged or ask your own question.