Finding the most profitable path

I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this.

To put it simply, the problem is the following:

• We want to go from point A to point B, nice and simple, we can easily find the shortest path.
• Each cell on our grid has a certain value, let's say we win some money by going through cells. So we do not want the shortest path but the most profitable one.
• But, we have a step limitation (known to be at least sufficient to make it from A to B). So we cannot just go on every cell, we have to find an optimized path.

Here is an example:

1, 2 and 3 represent cell values, the step limit is arbitrary but you get the idea.

The problem is: How to find the most valuable path we can take, and still make it to point B ?

Any thoughts on this?

• All the cells have positive weight $\geq 0$ right? Also are A and B always placed at the corners of your grid? Can i visit a cell twice and get the money twice (walking in a loop)? Oct 18 '21 at 8:13
• If you can move N, S, E, W but not diagonally, and visiting a cell multiple times only gives you the score once, then this is NP-complete by reduction from rectilinear TSP, so don't expect a poly-time algorithm. Oct 18 '21 at 12:28
• It could be FPT parameterized by the "above guarantee", i.e. finding the max-weight path with length $k+d$ from $s$ to $t$, where $d = \text{dist}_G(s,t)$, parameterized by $k$ (see e.g. $s$-$t$-detour problem). Oct 18 '21 at 13:04
• If the step limit is dist(s,t), then you can find the optimal solution in linear time. Oct 18 '21 at 13:16

The problem is NP-hard even in case of grid graphs and profits in $$\{0,1,2\}$$ by a reduction from Hamiltonian path on graphs that can be embedded on grids (the Hamiltonian path problem remains hard in this case).

Here is a sketch of the reduction. Embed the instance of the input graph on a grid (this can be done in polynomial time). Make sure the grid is fine enough and that all the edges become paths of the same length $$\ell \ge 2$$.

Assign a profit of $$1$$ to each cell corresponding to an edge. Assign a profit of $$2$$ to the cells corresponding to the vertices. Assign a profit of $$0$$ to all other cells. There exists an Hamiltonian path from $$s$$ to $$t$$ in the input graph if and only if the maximum profit of a path of length at most $$(n-1)\ell+n-1$$ that goes from the location corresponding to $$s$$ to the location corresponding to $$t$$ in the grid is $$2n + (n-1)\ell$$.

Here is an example with $$n=10$$ and $$\ell=2$$:

The best path of length at most $$(n-1)\ell + (n-1)=27$$ encounters exactly $$28$$ cells: all $$10$$ cells corresponding to vertices, plus $$28-10=18$$ cells corresponding to $$9$$ edges. It's total profit is $$10 \cdot 2 + 18 = 38$$. Notice that this is the best possible profit since we collect all cells with profit $$2$$ and no cell with profit $$0$$.

Note: It seems that you allow diagonal moves. The above construction might allow some vertices to be "shortcutted" by moving diagonally but this can be fixed. An easy way to do so is to "rotate" everything by 45 degrees, so that edges correspond to diagonal lines.

• I am not 100% sure, but I doubt this will work in a long "path-like" graph, where we "curl" the graph "backwards" at the middle point, and near the end node of this "path" expand it to have at least $2$ width. Now, a path on this graph will have to go through the entire string, going through the "middle node", and finishing at the end, while in the "grid" you can go through the $0$ tiles to create a shortcut to the end and possibly get more reward. Again, I'm not 100% sure this is a valid counter-example, and I think its at least worth to mention those kinds of "shortcuts", to avoid mistakes Oct 18 '21 at 12:51
• If you collect even a single $0$ tile then you won't be able to reach the desired profit (which is the sum of all tiles of profit $2$ with as many tiles of profit 1 as we are allowed to encounter before the returned path becomes too long). (Notice that in my previous version of the answer I let the profit of vertex-tiles be a parameter $M$. I have now fixed $M=2$ for simplicity). Oct 18 '21 at 12:54
• Are you sure, because if the graph is constructed in such a way that we cant go through its entirety with one path, then this "shortcut" does in fact prove problematic. I'm no expect in cubic graphs, so I have no idea if this is possible Oct 18 '21 at 13:11
• I'm not 100% sure I'm visualizing the graph you describe correctly but it seems that you want to skip some vertices. The number of visited cells of a path is at most $L=(n-1)\ell + n$. A Hamiltonian path collects the maximum possible profit of $P = 2 \cdot n + (L-n)$ since it traverses all tiles with profit $2$ (i.e., all vertices) and never touches a tile with profit $0$. If you skip at least one vertex then the maximum profit must be at most $2 \cdot (n-1) + (L-n+1) = P-1$. Similarly, if you ever touch a tile with profit $0$ the overall profit will be at most $2\cdot n + (L-n-1) = P-1$. Oct 18 '21 at 16:31
• Then my question is: is it guaranteed to have a Hamiltonian path in cubic graphs? Oct 18 '21 at 16:35