<p>Playing more <a href="https://play.google.com/store/apps/details?id=com.bigduckgames.flow&amp;hl=en" rel="nofollow noreferrer">Flow Free</a>, I think I've realized why I'm so amazingly brilliant at this game:</p>

<blockquote>
  <p>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).</p>
</blockquote>

<p>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.</p>

<blockquote>
  <p>What is the complexity of this problem?</p>
</blockquote>

<p>Without the promise, the problem becomes <a href="https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_239/_pdf" rel="nofollow noreferrer">NP-hard</a>, here is the <a href="https://cs.stackexchange.com/questions/31938/are-flow-free-puzzles-np-hard">related question</a> with many links.
(Note that the reduction in the above paper does not work for our promise version).</p>

<p>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.</p>

CC BY-SA 3.0
2017-01-09T10:11:13.613Z
Like UNAMBIGUOUS-SAT it is contained in [UP](https://en.wikipedia.org/wiki/UP_(complexity)) and probably, applying the same technique used in the [Valiant–Vazirani theorem](https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem), it could be proven that it remains a computational hard problem.
Marzio De Biasi
CC BY-SA 3.0
2017-01-09T10:30:42.140Z
@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.
domotorp
CC BY-SA 3.0
2017-01-09T10:34:22.993Z
@Ricky Indeed! I've played hundreds of puzzles of [this version](https://play.google.com/store/apps/details?id=com.bigduckgames.flowhexes&hl=en).
domotorp
CC BY-SA 3.0
2017-01-09T10:44:15.263Z
@domotorp: but you wrote "... 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..." so what is the "less restrictive problem" ? (perhaps, for better clarity, you could formally write the problem in the usual way: Input: ... Output: .... Promise: ...)
Marzio De Biasi
CC BY-SA 3.0
2017-01-09T11:14:28.437Z
It should be easy to modify hardness proof of Lynch to prove this.
Saeed
CC BY-SA 3.0
2017-01-09T13:17:22.953Z
@Saeed: Forgive my ignorance, but what Lynch?
domotorp
CC BY-SA 3.0
2017-01-09T15:47:57.787Z
@domotorp, I meant the very first paper on [hardness of disjoint paths](http://dl.acm.org/citation.cfm?id=1061430), as I understand your game (I didn't check the application), you have a real instance of disjoint paths problem. To the instance which lynch provided for planar graphs, add extra edges to make it grid and put both endpoints of those edges as terminals. To ensure there is a unique path, I guess a bit analysis on lynch's proof provides what you want.
Saeed
CC BY-SA 3.0
2017-01-09T15:52:16.720Z
BTW, I'm not sure if you promise that always there is a solution or you promise if there is a solution then it is unique, this is where I think it shouldn't be hard to get rid of this promise, it needs some works, but I guess not much thought.
Saeed
CC BY-SA 3.0
2017-01-09T15:54:54.253Z
unique path -> unique solution
Saeed
CC BY-SA 3.0
2017-01-09T19:32:13.327Z
@Saeed: I really don't think this helps much, but if you have a solution, you're welcome to post it as an answer.
domotorp
CC BY-SA 3.0
2017-01-09T23:18:49.003Z
@domtorp, Sorry I don't understand what do you mean. Why you think it doesn't help ... To me it is the first obvious approach. It was my suggestion, you can take it or leave it. Also unfortunately the question is not interesting for me to try to write the details.
Saeed
<cc.complexity-theory><np-hardness><puzzles>
How hard is PromiseFlowFree?
domotorp
# How hard is PromiseFlowFree?

(Asked by: username_0 on 2017-01-09)

Playing more [Flow Free](https://play.google.com/store/apps/details?id=com.bigduckgames.flow&hl=en), 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](https://www.jstage.jst.go.jp/article/ipsjjip/23/3/23_239/_pdf), here is the [related question](https://cs.stackexchange.com/questions/31938/are-flow-free-puzzles-np-hard) 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.

**Tags:** cc.complexity-theory, np-hardness, puzzles
> **Comments:**
> **username_1**: Like UNAMBIGUOUS-SAT it is contained in [UP](https://en.wikipedia.org/wiki/UP_(complexity)) and probably, applying the same technique used in the [Valiant–Vazirani theorem](https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem), it could be proven that it remains a computational hard problem.  
> **username_0**: @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.  
> **username_0**: @Ricky Indeed! I've played hundreds of puzzles of [this version](https://play.google.com/store/apps/details?id=com.bigduckgames.flowhexes&hl=en).  
> **username_1**: @domotorp: but you wrote "... 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..." so what is the "less restrictive problem" ? (perhaps, for better clarity, you could formally write the problem in the usual way: Input: ... Output: .... Promise: ...)  
> **username_2**: It should be easy to modify hardness proof of Lynch to prove this.  
> **username_0**: @Saeed: Forgive my ignorance, but what Lynch?  
> **username_2**: @domotorp, I meant the very first paper on [hardness of disjoint paths](http://dl.acm.org/citation.cfm?id=1061430), as I understand your game (I didn't check the application), you have a real instance of disjoint paths problem. To the instance which lynch provided for planar graphs, add extra edges to make it grid and put both endpoints of those edges as terminals. To ensure there is a unique path, I guess a bit analysis on lynch's proof provides what you want.  
> **username_2**: BTW, I'm not sure if you promise that always there is a solution or you promise if there is a solution then it is unique, this is where I think it shouldn't be hard to get rid of this promise, it needs some works, but I guess not much thought.  
> **username_2**: unique path -> unique solution  
> **username_0**: @Saeed: I really don't think this helps much, but if you have a solution, you're welcome to post it as an answer.  
> **username_2**: @domtorp, Sorry I don't understand what do you mean. Why you think it doesn't help ... To me it is the first obvious approach. It was my suggestion, you can take it or leave it. Also unfortunately the question is not interesting for me to try to write the details.  

---

## 0 answers

