6
$\begingroup$

Update:

This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.

http://www.youtube.com/watch?v=VbSwwos4R2E

I want to know if there is an efficient algorithm that allows me to visit every node in a planar graph with the minimum weight, revisiting allowed. Each node can have up to 4 linked nodes.

Graph Example

I uploaded the graph drawing as an example. In that example, one good route would be:

A - B - C - D - E - F - G - H - I - J - K - L - H - I - M

Summing weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 2 + 4 + 4 + 4 + 2 + 1 = 61

But another route, with less weight, would be:

A - B - C - D - E - F - G - H - I - M - I - H - L - K - J

Weights:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 1 + 1 + 2 + 4 + 4 + 4 = 60

Of course, I want to get the path with less weight. Revisited is allowed because otherwise I can't visit all nodes.

I'm not a Mathematician myself so easy talk would be much appreciated. I'm familiar with algorithms like A* and Dijkstra, that algorithms are useful when I have a target to search, but in this case I'm not searching a particular target.

Thanks!

$\endgroup$
  • 2
    $\begingroup$ This is too basic to be suitable on cstheory.stackexchange.com, and it is a cross-post of math.stackexchange.com/questions/55221/…. Voted to close as off topic. $\endgroup$ – Tsuyoshi Ito Aug 3 '11 at 22:51
  • 3
    $\begingroup$ Oops. I may have voted to close too quickly. If it is guaranteed that the input graph is planar, I do not know if the question is too basic or not, and I definitely cannot claim that it is too basic because I do not know the answer. $\endgroup$ – Tsuyoshi Ito Aug 3 '11 at 23:21
  • 1
    $\begingroup$ I took the liberty of editing the question to add some important information from the later part of the question and your comments to the beginning of the question. I hope you do not mind. I cannot cancel the vote, but I virtually take back my vote. $\endgroup$ – Tsuyoshi Ito Aug 3 '11 at 23:51
  • 3
    $\begingroup$ I think this question is a mess. I would edit it, but I would completely change it to: Title: Finding the cheapest path containing all vertices Question: What is the best known algorithm for finding a path of minimum cost in a weighted, planar graph of maximum degree 4? $\endgroup$ – Tyson Williams Aug 3 '11 at 23:59
  • 1
    $\begingroup$ @Tyson: I may have created a mess, but my intent was to prevent other people from misunderstanding in the same way as me while changing the question as little as possible. The rest is up to Veehmot. (But this may be a moot point now that mhum already answered the question.) $\endgroup$ – Tsuyoshi Ito Aug 4 '11 at 2:28
14
$\begingroup$

According to this abstract, deciding whether a 4-regular planar graph has a Hamiltonian Path is NP-complete.

Edited to add: Call a path that is allowed to revisit nodes a walk. Let $G$ be a graph on $n$ vertices and let us impose a weight of 1 on each edge. Then, $G$ has a Hamiltonian path if and only if the minimum weight walk in G visiting each vertex has weight $n-1$. In other words, if you can compute the minimum weight of a Hamiltonian walk, you can can detect the existence of Hamiltonian paths.

$\endgroup$
  • 3
    $\begingroup$ OP is not looking for a Hamiltonian Path but for a path that contains all vertices (i.e. vertices can be reused). $\endgroup$ – Tyson Williams Aug 4 '11 at 0:03
  • 3
    $\begingroup$ Nice answer. Nitpicking: “weight n” should be “weight n−1.” $\endgroup$ – Tsuyoshi Ito Aug 4 '11 at 0:59
  • 3
    $\begingroup$ @Veehmot: there is no efficient solution. Let me say again what mhum said. Suppose we could compute optimal walks, like you asked for, but for general graphs. Take a graph with $n$ vertices, put $1$'s on all edges, compute optimum walk. If its weight is $n-1$ then you managed to visit every vertex exactly once, so the graph is Hamiltonian. If the graph is not Hamiltonian, then the optimum walk cannot have weight $n-1$ because it must visit some vertex at least twice. But your graphs are not general, they are planar of degree 4. That's why mhum cited the relevant paper showing it's still hard. $\endgroup$ – Andrej Bauer Aug 4 '11 at 5:37
  • 2
    $\begingroup$ Andrej, there is not efficient exact algorithm assuming P$\neq$NP. So there may be decent approximations/stochastic algorithms, and there might even be an efficient algorithm we have not found yet. (I am sure you are aware of that, but Veehmot might not be.) $\endgroup$ – Raphael Aug 4 '11 at 5:45
  • 2
    $\begingroup$ Not sure what "resolved" means in this case. $\endgroup$ – Suresh Venkat Aug 5 '11 at 4:14

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.