5
$\begingroup$

This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals). For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4.

8 2 4

0 7 1

3 7 9

The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

If all numbers are distinct then you can find the longest path using straightforward dynamic programming. The general problem is probably NP-complete, since deciding whether a grid graph has a Hamilton path is NP-complete, as shown by Itai, Papadimitriou and Szwarcfiter. Grid graphs are finite induced subgraphs of the infinite rectangular grid, in which non-diagonal cells are not adjacent; however it seems reasonable to conjecture that Hamilton path is NP-complete also for finite subgraphs of the infinite rectangular grid with diagonals. Given that, it is likely that your problem is also NP-complete.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I believe the SO problem has a rectangular grid (width $\times$ height), and the grid squares are filled with numbers, so not so sure. If the problem is a general sub-graph of numbers, then I believe your assertion of NP-Hardness might be true. Given a grid graph (whose hamiltonian path we want), replace a grid square with a $3\times3$ square and fill it with $$0 1 0$$ $$1 1 1$$ $$0 1 0$$ and I believe you have a reduction to this problem (haven't tried proving anything, though). $\endgroup$
    – Aryabhata
    Commented May 24, 2013 at 7:15
  • $\begingroup$ Yes, If you see my answer on SO, I also believe this, because this two are very similar to each other. But to be honest this isn't a proof, I think there should be an elegant reduction. $\endgroup$
    – user742
    Commented May 24, 2013 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.