Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I stumbled on an open problem posed by David Eppstein and I am interested in its complexity status. He conjectured that it is NP-complete.

Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ 0’s and 1’s

Question: Is there a path through adjacent matrix entries, covering each matrix entry exactly once, with values matching the given sequence?

Did anyone prove that the problem is indeed hard?

share|improve this question

1 Answer 1

up vote 12 down vote accepted

I received an email last February from a Spanish undergraduate, Nil Mamano, with a proof that this problem is indeed NP-complete, by reduction from Hamiltonian path in grid graphs. I don't know that it has been published anywhere yet. The reduction replaces each vertex of the grid graph by a 2x2 block of 1's, and each edge, face, or missing vertex by a 2x2 block of 0's. The input sequence alternates between subsequences of four 1's and four 0's for as many times as is needed to cover all the vertices, then fills out the rest of the sequence with 0's. To match the input sequence, a path through the grid must align the subsequences of four 1's with the 2x2 blocks of 1's from the reduction, forming a Hamiltonian path; if such a path exists, it's always possible to do this in a way that allows the rest of the matrix to be covered by the remaining zeros at the end of the sequence.

share|improve this answer
    
Thanks David for sharing this interesting resolution. –  Mohammad Al-Turkistany Jun 28 at 7:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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