6

While formalizing the gadgets for the proposed reduction of the question 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
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).

Community
  • 1
Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127

1 Answers1

4

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.

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

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.

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

Community
  • 1
Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • Hamiltonian path on grid graphs isn't NP-complete. Every grid graph has a Hamiltonian path. – David Richerby Sep 25 '13 at 23:22
  • @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 Sep 26 '13 at 07:36
  • @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 Sep 26 '13 at 08:24
  • @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 Sep 26 '13 at 09:53
  • 1
    @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 Sep 26 '13 at 09:54
  • @MarzioDeBiasi "The reduction is from Hamiltonian path on grid graphs." A clarifying edit would help, I think. – David Richerby Sep 26 '13 at 09:56
  • @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 Sep 26 '13 at 10:09
  • @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 Sep 26 '13 at 15:46
  • @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 Sep 26 '13 at 15:57
  • 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. – David Richerby Sep 26 '13 at 16:08
  • 1
    @DavidRicherby: ok, I included the definition in the answer. – Marzio De Biasi Sep 26 '13 at 16:21