Proving NP-completeness for a not so cheesy problem

Question

Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. The mouse can move from a given positon (i, j) either in the direction (i+1, j) or (i, j+1). When the mouse visits a given position (i,j), it collects all the given cheese immediately, so if it decides to return to an already visited position, it will already be empty. Additionally, the mouse can ONLY reverse/back ONCE when traversing the matrix, because we can assume that this mouse doesn't particularly like to change its mind.

So given all these prerequisites, the question is whether or not it is possible for the mouse to collect exactly A pieces of cheese, starting from the position (1,1) and ending up in the position (B,B)?

There should be a proof that this problem is NP-complete by showing it is in NP and by reducing the NP-complete problem Subset Sum.

For showing it is in NP I was thinking about maybe looping through the whole matrix and counting the total number of cheese and then maybe have some sort of boolean condition to check whether or not the amount of cheese the mouse has collected equals to the total amount of cheese located in the matrix and that this will take polynomial time to do. However, I am not sure this is the right way to do and I am even more unsure of how to reduce Subset Sum to this problem. Thus, I am grateful for your help and advice!

Answer 1

The problem is in $NP$ since a certificate is the path itself, which has length at most $2B-1 + 2 = 2B+1$.

Given an instance $\langle S, k\rangle$ of subset sum where $S = \{x_1, \dots, x_n\}$ is a set of integers and $k$ is the target value, you can create an instance of your problem by choosing: $B=n+2$, $M = \mbox{diag}(0, x_1, x_2, \dots, x_n, 0)$, and $A = k$.

Clearly any path in $M$ that collects $A$ pieces of cheese implies the existence of a subset $S' \subseteq S$ such that $\sum_{x_i} x_i = A = k$.

On the converse notice that, given any $S' \subseteq S$ satisfying $\sum_{x_i} x_i = k$, it is possible to find a path $P$ in $M$ with the sought constraints (actually, backtracking is not even required) that traverses $M[i+1, i+1]$ if and only if $x_i \in S'$. This shows that pieces of cheese collected by $P$ are exactly $k=A$.

Also notice that your problem can be solved by pseudopolynomial-time dynamic programming algorithm having complexity $O(A \cdot B^2)$.