10
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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.

$\endgroup$

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.