<p>I tried to write a formal proof of the NP-completeness of Problem 1 (Crazy Frog Problem, CFP).</p>

<p>It remains NP-complete even if restricetd to a one dimensional board (1-D Crazy Frog Problem, 1-D CFP) or to a one dimensional board without blocked cells, and there is an immediate reduction from the 1-D CFP without blocked cells to the <a href="https://cstheory.stackexchange.com/questions/18255/efficient-algorithm-for-existence-of-permutation-with-differences-sequence">Permutation Reconstruction from Differences sequence problem</a>.</p>

<p>The reduction is from Hamiltonian path on grid graphs (a grid graph is a node-induced finite subgraph of the infinite grid: if two nodes are adjacent (distance 1 in the grid) then there is an edge between them; a grid graph can have <em>holes</em>, i.e. some nodes may be missing;  see "Hamilton Paths in Grid Graphs" by Alon Itai, Christos H. Papadimitriou, Jayme L. Szwarcfiter). Given a grid graph $G$ that fits in a $w \times w$ square, with nodes $u_i$ at coordinates $(x_{u_i},y_{u_i})$
and source, target nodes $s,t$; build a filled board of size $4n\times4n$ with all blocked cells except cells $(4x_{u_i},4y_{u_i})$ and target cell $(4x_t+1,4y_t)$. The initial frog position is $(4x_s,4y_s)$. This part of the board is called <em>graph area</em>. The first "logical" sequence of moves is the following sequence repeated $|V| - 1$ times:</p>

<p>(suppose that frog is in position $(x,y)$)</p>

<ul>
<li>$(0,J_i)$: vertically jump to an empty part of the board (<em>edge gadget</em>)</li>
<li>$(-2,2)$: make a backward diagonal jump of length 2</li>
<li>$(0,p)$: vertically jump to another empty part of the board (on the same gadget)</li>
<li>$(2,2)$: make a forward diagonal jump of length 2</li>
<li>$(0,J_i+p)$: return to graph area in one of the cells $(x+4,y),(x-4,y),(x,y-4),(x,y+4)$</li>
</ul>

<p>This forces the frog to make $n-1$ steps on the empty cells corresponding to the nodes of the original graph.</p>

<p>The sequence is followed by one horizontal step $(1,0)$ (that forces the last cell to be the one associated with the target node $t$) and a forced step that leads to a <em>cleanup gadget</em>. The sequence of jumps of the cleanup gadget allows it to visit all unvisited cells of the edge gadgets and completely fill the board.</p>

<p>This is a simple graphical outline of the gadgets used in the reduction:</p>

<p><img src="https://i.sstatic.net/Aokk2.png" alt="enter image description here"></p>

<p>Figure: <em>Outline of a CFP instance (for better readability blocked cells are not shown, the cleanup gadget is not complete and space is compacted ). Black jumps represent the graph area traversal, green jumps represent the edge gadgets traversals, red jumps represent the vertical selection gadget traversal, blue jumps represent the horizontal hole gadget traversal.</em></p>

<p>The details can be found in the draft paper <a href="http://www.fractalmuse.org/vdisk/cstheory/crazyfrog.pdf" rel="nofollow noreferrer">"The Crazy Frog Problem and Permutation Reconstruction from Differences" that can be download here</a>.</p>

<p>The reduction is complex so perhaps it is wrong (or can be simplified), but I think that the results (if new?) are interesting ...</p>

CC BY-SA 3.0
2013-09-25T23:22:00.557Z
Hamiltonian path on grid graphs isn't NP-complete. Every grid graph has a Hamiltonian path.
David Richerby
CC BY-SA 3.0
2013-09-26T07:36:52.500Z
@DavidRicherby, Hamiltonin path on grid graphs is NP-Hard, note that grid graph is just a subset of infinite grid, on the other hand on solid grids ($n\times n$) finding Hamiltonian path is trivial. And in this answer Marzio used solid grid graph, which is wrong.
Saeed
CC BY-SA 3.0
2013-09-26T08:24:57.257Z
@Saeed Then we seem to be disagreeing about terminology. Every reference I can see defines a grid graph to have vertices $\{1, \dots, m\}\times \{1, \dots, n\}$ and edges from $(x,y)$ to $(x+1,y)$ and $(x,y+1)$ for all appropriate $x$ and $y$. Clearly, any such graph has a Hamiltonian path; I agree that it's NP-complete to determine if subgraphs of these graphs have Hamiltonian paths (reduction from Hamiltonian paths of planar graphs with maximum degree 4).
David Richerby
CC BY-SA 3.0
2013-09-26T09:53:52.300Z
@DavidRicherby: Hamiltonian path (and cycle) on grid graphs *with "holes"* is NP-Complete. I didn't used a solid grid graph in my reduction (the Graph area contain (many) blocked cells).
Marzio De Biasi
CC BY-SA 3.0
2013-09-26T09:54:10.897Z
@Saeed: Hamiltonian path (and cycles) on grid graphs *with "holes"* is NP-Complete. I didn't used a solid grid graph in my reduction (the Graph Area contain (many) blocked cells).
Marzio De Biasi
CC BY-SA 3.0
2013-09-26T09:56:15.800Z
@MarzioDeBiasi "The reduction is from Hamiltonian path on grid graphs." A clarifying edit would help, I think.
David Richerby
CC BY-SA 3.0
2013-09-26T10:09:09.430Z
@DavidRicherby: the "with holes" is implied by the definition of grid graph: a grid graph is a node-induced finite subgraph of the infinite grid: if two nodes are adjacent (distance 1 in the grid) then there is an edge between them, but some nodes may be missing.
Marzio De Biasi
CC BY-SA 3.0
2013-09-26T15:46:16.863Z
@MarzioDeBiasi, Actually definition of grid graph is what I wrote, and the grid graph with hole (by your definition) is actually grid graph. I see you said $k\times k$ grid, I didn't read thorough, and I thought is solid grid graph.
Saeed
CC BY-SA 3.0
2013-09-26T15:57:33.293Z
@DavidRicherby, I think we are looking into different references, but e.g just look at first line of this reference: http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf , there are many similar references for definition of grid graphs.
Saeed
CC BY-SA 3.0
2013-09-26T16:08:02.560Z
I think that, given the confusion over exactly what a grid graph is (for example, Diestel and Wikipedia agree with the definition I gave; Itai _et al._ and others agree with the definition you gave), it would be a good idea to explicitly define what it meant by "grid graph" in the answer. That way, people won't have to read the comments to understand it.
David Richerby
CC BY-SA 3.0
2013-09-26T16:21:22.317Z
@DavidRicherby: ok, I included the definition in the answer.
Marzio De Biasi
CC BY-SA 3.0
2013-07-28T23:35:56.033Z
2013-09-26T16:20:57.390Z
2017-04-13T12:32:28.053Z
Marzio De Biasi
<p>While formalizing the gadgets for the proposed reduction of the question 
<a href="https://cstheory.stackexchange.com/questions/18255/efficient-algorithm-for-existence-of-permutation-with-differences-sequence">Efficient algorithm for existence of permutation with differences sequence?</a> the following problems came to my mind:</p>

<p><strong>Problem 1</strong> (I call it the "crazy frog problem" :-))</p>

<p>Given a $n \times n$ partially filled board (some cells are <em>empty</em>, some are already <em>filled</em>), a <em>starting cell</em> $c_0 = (x_0,y_0)$ and a list of <em>jump distances</em> $(\Delta x_1,\Delta y_1),(\Delta x_2,\Delta y_2),...,(\Delta x_m, \Delta y_m),\; -n &lt; \Delta x_i, \Delta y_i &lt; n$; is there a sequence $(s_1,s_2,...,s_m), s_i \in \{+1,-1\}$ such that the sequence of 
jumps: $$c_j = ( x_{j-1} + \Delta x_j * s_j, \quad y_{j-1} + \Delta y_j * s_j ) $$</p>

<p>makes the frog visit every empty cell of the board exactly once? (every jump must be within the boundaries of the board, at every jump the target cell must be empty, after the jump the cell becomes filled)</p>

<p><img src="https://i.sstatic.net/qbFNV.png" alt="enter image description here"><br>
<em>Figure 1. An instance of the CFP on the left and its solution on the right.</em></p>

<p><strong>Problem 2</strong></p>

<p>What is the complexity of the Hamiltonian path problem on grid graphs with holes, if we force the path to be an alternating sequence of horizontal/vertical moves (i.e. two consecutive horizontal/vertical moves along the path are forbidden).</p>

<blockquote>
Are these problems already known and what is their complexity?
</blockquote>

<p><br>
Notes: there is an immediate reduction from problem 2 to problem 1; probably there is a reduction from problem 1 to the problem of finding a valid permutation from a difference sequence (which I'm trying to prove NPC).</p>

<cc.complexity-theory><hamiltonian-paths>
Two Hamiltonian path problem variants
Marzio De Biasi
# Two Hamiltonian path problem variants

(Asked by: username_0 on 2013-07-23)

While formalizing the gadgets for the proposed reduction of the question
[Efficient algorithm for existence of permutation with differences sequence?](https://cstheory.stackexchange.com/questions/18255/efficient-algorithm-for-existence-of-permutation-with-differences-sequence) the following problems came to my mind:

**Problem 1** (I call it the "crazy frog problem" :-))

Given a $n \times n$ partially filled board (some cells are *empty*, some are already *filled*), a *starting cell* $c\_0 = (x\_0,y\_0)$ and a list of *jump distances* $(\Delta x\_1,\Delta y\_1),(\Delta x\_2,\Delta y\_2),...,(\Delta x\_m, \Delta y\_m),\; -n < \Delta x\_i, \Delta y\_i < n$; is there a sequence $(s\_1,s\_2,...,s\_m), s\_i \in \{+1,-1\}$ such that the sequence of
jumps: $$c\_j = ( x\_{j-1} + \Delta x\_j \* s\_j, \quad y\_{j-1} + \Delta y\_j \* s\_j ) $$

makes the frog visit every empty cell of the board exactly once? (every jump must be within the boundaries of the board, at every jump the target cell must be empty, after the jump the cell becomes filled)

![enter image description here](https://i.sstatic.net/qbFNV.png)  
*Figure 1. An instance of the CFP on the left and its solution on the right.*

**Problem 2**

What is the complexity of the Hamiltonian path problem on grid graphs with holes, if we force the path to be an alternating sequence of horizontal/vertical moves (i.e. two consecutive horizontal/vertical moves along the path are forbidden).

> Are these problems already known and what is their complexity?

Notes: there is an immediate reduction from problem 2 to problem 1; probably there is a reduction from problem 1 to the problem of finding a valid permutation from a difference sequence (which I'm trying to prove NPC).

**Tags:** cc.complexity-theory, hamiltonian-paths

---

## 1 answers

### Answer by username_0 on 2013-07-28. Score: 4 | Accepted answer

I tried to write a formal proof of the NP-completeness of Problem 1 (Crazy Frog Problem, CFP).

It remains NP-complete even if restricetd to a one dimensional board (1-D Crazy Frog Problem, 1-D CFP) or to a one dimensional board without blocked cells, and there is an immediate reduction from the 1-D CFP without blocked cells to the [Permutation Reconstruction from Differences sequence problem](https://cstheory.stackexchange.com/questions/18255/efficient-algorithm-for-existence-of-permutation-with-differences-sequence).

The reduction is from Hamiltonian path on grid graphs (a grid graph is a node-induced finite subgraph of the infinite grid: if two nodes are adjacent (distance 1 in the grid) then there is an edge between them; a grid graph can have *holes*, i.e. some nodes may be missing; see "Hamilton Paths in Grid Graphs" by Alon Itai, Christos H. Papadimitriou, Jayme L. Szwarcfiter). Given a grid graph $G$ that fits in a $w \times w$ square, with nodes $u\_i$ at coordinates $(x\_{u\_i},y\_{u\_i})$
and source, target nodes $s,t$; build a filled board of size $4n\times4n$ with all blocked cells except cells $(4x\_{u\_i},4y\_{u\_i})$ and target cell $(4x\_t+1,4y\_t)$. The initial frog position is $(4x\_s,4y\_s)$. This part of the board is called *graph area*. The first "logical" sequence of moves is the following sequence repeated $|V| - 1$ times:

(suppose that frog is in position $(x,y)$)

* $(0,J\_i)$: vertically jump to an empty part of the board (*edge gadget*)
* $(-2,2)$: make a backward diagonal jump of length 2
* $(0,p)$: vertically jump to another empty part of the board (on the same gadget)
* $(2,2)$: make a forward diagonal jump of length 2
* $(0,J\_i+p)$: return to graph area in one of the cells $(x+4,y),(x-4,y),(x,y-4),(x,y+4)$

This forces the frog to make $n-1$ steps on the empty cells corresponding to the nodes of the original graph.

The sequence is followed by one horizontal step $(1,0)$ (that forces the last cell to be the one associated with the target node $t$) and a forced step that leads to a *cleanup gadget*. The sequence of jumps of the cleanup gadget allows it to visit all unvisited cells of the edge gadgets and completely fill the board.

This is a simple graphical outline of the gadgets used in the reduction:

![enter image description here](https://i.sstatic.net/Aokk2.png)

Figure: *Outline of a CFP instance (for better readability blocked cells are not shown, the cleanup gadget is not complete and space is compacted ). Black jumps represent the graph area traversal, green jumps represent the edge gadgets traversals, red jumps represent the vertical selection gadget traversal, blue jumps represent the horizontal hole gadget traversal.*

The details can be found in the draft paper ["The Crazy Frog Problem and Permutation Reconstruction from Differences" that can be download here](http://www.fractalmuse.org/vdisk/cstheory/crazyfrog.pdf).

The reduction is complex so perhaps it is wrong (or can be simplified), but I think that the results (if new?) are interesting ...

> **Comments:**
> **username_1**: Hamiltonian path on grid graphs isn't NP-complete. Every grid graph has a Hamiltonian path.  
> **username_2**: @DavidRicherby, Hamiltonin path on grid graphs is NP-Hard, note that grid graph is just a subset of infinite grid, on the other hand on solid grids ($n\times n$) finding Hamiltonian path is trivial. And in this answer Marzio used solid grid graph, which is wrong.  
> **username_1**: @Saeed Then we seem to be disagreeing about terminology. Every reference I can see defines a grid graph to have vertices $\{1, \dots, m\}\times \{1, \dots, n\}$ and edges from $(x,y)$ to $(x+1,y)$ and $(x,y+1)$ for all appropriate $x$ and $y$. Clearly, any such graph has a Hamiltonian path; I agree that it's NP-complete to determine if subgraphs of these graphs have Hamiltonian paths (reduction from Hamiltonian paths of planar graphs with maximum degree 4).  
> **username_0**: @DavidRicherby: Hamiltonian path (and cycle) on grid graphs *with "holes"* is NP-Complete. I didn't used a solid grid graph in my reduction (the Graph area contain (many) blocked cells).  
> **username_0**: @Saeed: Hamiltonian path (and cycles) on grid graphs *with "holes"* is NP-Complete. I didn't used a solid grid graph in my reduction (the Graph Area contain (many) blocked cells).  
> **username_1**: @MarzioDeBiasi "The reduction is from Hamiltonian path on grid graphs." A clarifying edit would help, I think.  
> **username_0**: @DavidRicherby: the "with holes" is implied by the definition of grid graph: a grid graph is a node-induced finite subgraph of the infinite grid: if two nodes are adjacent (distance 1 in the grid) then there is an edge between them, but some nodes may be missing.  
> **username_2**: @MarzioDeBiasi, Actually definition of grid graph is what I wrote, and the grid graph with hole (by your definition) is actually grid graph. I see you said $k\times k$ grid, I didn't read thorough, and I thought is solid grid graph.  
> **username_2**: @DavidRicherby, I think we are looking into different references, but e.g just look at first line of this reference: http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf , there are many similar references for definition of grid graphs.  
> **username_1**: I think that, given the confusion over exactly what a grid graph is (for example, Diestel and Wikipedia agree with the definition I gave; Itai _et al._ and others agree with the definition you gave), it would be a good idea to explicitly define what it meant by "grid graph" in the answer. That way, people won't have to read the comments to understand it.  
> **username_0**: @DavidRicherby: ok, I included the definition in the answer.  

---

