# Find the cheapest cycle through two points on a rectangular grid

I have a task, but I have no idea how to solve it.

We have to find a cycle going through $(1,1)$ and $(n,n)$ (X axis on the picture is indexed right to left) such that the sum of values in cells is minimized. A cycle can't contain a cell more than once.

Example:

• Your example doesn't go through the cell (n,n) (assuming n is the size of the field). Please clarify.
– jkff
Oct 4 '14 at 20:10
• In my example we have (n,n) = (3,3). The field (3,3) has value 8, field (1,1) has value 23 Oct 4 '14 at 21:32
• Ah, didn't realize you were indexing right to left. That's confusing because matrices are usually indexed left to right; I believe language-specific directionality rules do not apply here. Interesting problem anyway; basically you need to find two non-intersecting paths - AB and BA - with the smallest total weight. I suspect it may be NP-hard, but I need to think more.
– jkff
Oct 5 '14 at 2:22
• It should be easy to set up an NP-completeness reduction from Hamiltonian cycle in grid graphs (using negative numbers in an evenly spaced subgrid to force the optimal tour to go through all of the cells in the subgrid, and positive numbers elsewhere as barriers to make the Hamiltonian cycle better than other cycles). Oct 5 '14 at 7:01
• @David Eppstein, tell me more, please Oct 5 '14 at 12:24

Not quite the original question, but in case it's useful: If the weights are positive and unary, this is the same problem as "Shortest Two Disjoint Paths", which is in $P$.
For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?