<p>I am working on my research problem that essentially boils down to the following question. Consider an <span class="math-container">$N \times N$</span> matrix. There is a man at given a starting point <span class="math-container">$(x,y)$</span>. In each unit of time, the man can move east, west, north or south of the point (no diagonal moves). Given an end point <span class="math-container">$(p,q)$</span> and <span class="math-container">$K$</span>, the goal is to reach <span class="math-container">$(p,q)$</span> in at most <span class="math-container">$K$</span> 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'.</p>

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

<p>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!</p>

CC BY-SA 4.0
2020-05-05T01:59:40.790Z
Hint: use the NP-hardness of path TSP on grid graphs. See theorem 2.1 of https://epubs.siam.org/doi/abs/10.1137/0211056 .
Yonatan N
CC BY-SA 4.0
2020-05-05T02:13:35.553Z
@YonatanN Thanks!!
karmanaut
CC BY-SA 4.0
2020-05-07T20:22:41.143Z
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?
Neal Young
CC BY-SA 4.0
2021-01-27T10:06:25.723Z
@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.
Mikhail Rudoy
CC BY-SA 4.0
2021-01-28T13:47:28.223Z
@MikhailRudoy, good point..
Neal Young
<ds.algorithms><graph-algorithms><np-hardness>
NP-Hard or PTIME?
karmanaut
# NP-Hard or PTIME?

(Asked by: username_0 on 2020-05-04)

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!

**Tags:** ds.algorithms, graph-algorithms, np-hardness

> **Comments:**
> **username_1**: Hint: use the NP-hardness of path TSP on grid graphs. See theorem 2.1 of https://epubs.siam.org/doi/abs/10.1137/0211056 .  
> **username_0**: @YonatanN Thanks!!  
> **username_2**: 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?  
> **username_3**: @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.  
> **username_2**: @MikhailRudoy, good point..  

---

## 0 answers

