1
$\begingroup$

The problem:

Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$)

Output:

YES if there exists a path through adjacent matrix entries $\dagger$, starting at pos, covering each matrix entry with a 1 exactly once, and not covering the matrix entries with a 0.

NO otherwise.

$\dagger$ a matrix entry is adjacent to the one immediately to its left, to the one immediately to its right, to the one immediately upwards and the one immediately below.


Informally, the matrix can be seen as a labyrinth where the 0's are walls, you start somewhere, and you have to walk through the whole maze without repeating any position.

Example input:

1100
1100
0000
0001
Pos: (1,1)

Corresponding output:

No (because you can't reach the position (4,4))

Is this problem NP-complete? If it is, what other NP-complete problem has been reduced to it? If it isn't, what approach can I use to design an efficient algorithm?

I think this is a particular case of the hamiltonian path problem (except that you have a fixed starting point). The graph can be constructed by taking the matrix entries with 1's as vertices. 2 vertices are adjacent iff their corresponding matrix entries are adjacent. So I think that reducing this problem to the hamiltonian path problem should be easy. Of course, to prove it is NP-complete, we would have to do the reduction backwards.

$\endgroup$
1
$\begingroup$

Your problem is to determine if there is a Hamiltonian path in a grid graph (an induced subgraph of a rectangular grid). This is NP-complete: see Itai, Papadimitriou and Szwarcfiter, Hamilton Paths in Grid Graphs (SIAM J. Comput., 11(4):676–686, 1982) PDF.

$\endgroup$
  • 1
    $\begingroup$ Does the fact that there is a fixed entry point change this result? $\endgroup$ – nmamg Feb 10 '14 at 23:30
  • $\begingroup$ @nmamg Good point. The reduction in Ital et al. creates graphs with long "strips" of squares between vertex gadgets; there's probably enough space to add an edge to a vertex of degree 1, to force the path to start in a specific place. $\endgroup$ – David Richerby Feb 11 '14 at 0:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.