<p>Ok, here's a reduction from Hamiltonian cycles in grid graphs to your problem. It requires the grid graph to have vertices in the two opposite corners but that shouldn't be an obstacle to getting the details to work.</p>

<p><img src="https://i.sstatic.net/7ZFSi.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-10-05T17:59:34.043Z
2014-10-05T17:59:34.043Z
David Eppstein
<p>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$.</p>

<p><a href="https://cstheory.stackexchange.com/questions/21987/for-which-values-of-k-is-minimum-length-undirected-k-disjoint-paths-in-mat">For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?</a></p>

<p>Björklund, Andreas, and Thore Husfeldt. "Shortest Two Disjoint Paths in Polynomial Time." Automata, Languages, and Programming. Springer Berlin Heidelberg, 2014. 211-222.</p>

<p><a href="http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf" rel="nofollow noreferrer">http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf</a></p>

CC BY-SA 3.0
2014-10-05T20:54:09.353Z
2014-10-05T20:54:09.353Z
2017-04-13T12:32:28.743Z
Geoffrey Irving
<p>I have a task, but I have no idea how to solve it.</p>

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

<p>Example:</p>

<p><img src="https://i.sstatic.net/MXhtu.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-10-04T20:10:44.250Z
Your example doesn't go through the cell (n,n) (assuming n is the size of the field). Please clarify.
jkff
CC BY-SA 3.0
2014-10-04T21:32:53.220Z
In my example we have (n,n) = (3,3). The field (3,3) has value 8, field (1,1) has value 23
xaweyNEW
CC BY-SA 3.0
2014-10-05T02:22:08.847Z
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
CC BY-SA 3.0
2014-10-05T07:01:04.843Z
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).
David Eppstein
CC BY-SA 3.0
2014-10-05T12:24:43.280Z
@David Eppstein, tell me more, please
xaweyNEW
<graph-algorithms>
Find the cheapest cycle through two points on a rectangular grid
xaweyNEW
# Find the cheapest cycle through two points on a rectangular grid

(Asked by: username_0 on 2014-10-04)

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:

![enter image description here](https://i.sstatic.net/MXhtu.png)

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: Your example doesn't go through the cell (n,n) (assuming n is the size of the field). Please clarify.  
> **username_0**: In my example we have (n,n) = (3,3). The field (3,3) has value 8, field (1,1) has value 23  
> **username_1**: 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.  
> **username_2**: 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).  
> **username_0**: @David Eppstein, tell me more, please  

---

## 2 answers

### Answer by username_2 on 2014-10-05. Score: 8

Ok, here's a reduction from Hamiltonian cycles in grid graphs to your problem. It requires the grid graph to have vertices in the two opposite corners but that shouldn't be an obstacle to getting the details to work.

![enter image description here](https://i.sstatic.net/7ZFSi.png)


---

### Answer by username_3 on 2014-10-05. Score: 3

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}$?](https://cstheory.stackexchange.com/questions/21987/for-which-values-of-k-is-minimum-length-undirected-k-disjoint-paths-in-mat)

Björklund, Andreas, and Thore Husfeldt. "Shortest Two Disjoint Paths in Polynomial Time." Automata, Languages, and Programming. Springer Berlin Heidelberg, 2014. 211-222.

<http://thorehusfeldt.files.wordpress.com/2010/08/spdp-e5d5661.pdf>


---

