I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the man can move east, west, north or south of the point (no diagonal moves). Given an end point $(p,q)$ and $K$, the goal is to reach $(p,q)$ in at most $K$ steps such that the path taken maximizes the number of blocks 'visited' by the man. There is no constraint on the structure of the path taken (it can contain cycles or revisit the same block again). A block is said to be 'visited' if the man has never been to the said block before and he then goes to the block. Revisiting a 'visited' block does not increase the count of total blocks 'visited'.

Another variant of the problem is when instead of one man, there are $\ell$ men, each of whom want to reach $(p,q)$ in at most $K$ steps while maximizing the total number of blocks visited by all of them.

I thought that a simple DP algorithm would suffice to solve it but now I am suspecting that this problem is NP-hard but can't show that either. Any leads appreciated!

  • 1
    $\begingroup$ Hint: use the NP-hardness of path TSP on grid graphs. See theorem 2.1 of epubs.siam.org/doi/abs/10.1137/0211056 . $\endgroup$
    – Yonatan N
    May 5, 2020 at 1:59
  • $\begingroup$ @YonatanN Thanks!! $\endgroup$
    – karmanaut
    May 5, 2020 at 2:13
  • 1
    $\begingroup$ Are you considering the $N\times N$ matrix to be an $N\times N$ two-dimensional grid graph with all $N^2$ vertices and all $2N^2-O(N)$ edges present (i.e., each internal node has four edges)? And by "block" do you mean a vertex in this graph? If so, isn't there always a path that visits $\min(K, N\times N)$ blocks (which is optimal)? If not, can you give an example that illustrates why the problem is hard? $\endgroup$
    – Neal Young
    May 7, 2020 at 20:22
  • $\begingroup$ @NealYoung I can think of a simple counterexample to your $min(K, N\times N)$ idea using parity. If the start point and end point are adjacent but $K=2$, the only way to reach the end point is to still go directly there (and not use the second step), resulting in only one visited location (rather than 2 as your expression would suggest). I agree though that this problem doesn't seem hard outside of this kind of parity issue. $\endgroup$ Jan 27, 2021 at 10:06
  • $\begingroup$ @MikhailRudoy, good point.. $\endgroup$
    – Neal Young
    Jan 28, 2021 at 13:47


Your Answer

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