4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Your example doesn't go through the cell (n,n) (assuming n is the size of the field). Please clarify. $\endgroup$
    – jkff
    Oct 4 '14 at 20:10
  • $\begingroup$ In my example we have (n,n) = (3,3). The field (3,3) has value 8, field (1,1) has value 23 $\endgroup$
    – xaweyNEW
    Oct 4 '14 at 21:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – jkff
    Oct 5 '14 at 2:22
  • 6
    $\begingroup$ 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). $\endgroup$ Oct 5 '14 at 7:01
  • $\begingroup$ @David Eppstein, tell me more, please $\endgroup$
    – xaweyNEW
    Oct 5 '14 at 12:24
8
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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}$?

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.