<p>According to <a href="http://www.sciencedirect.com/science/article/pii/0304397594901856">this abstract</a>, deciding whether a 4-regular planar graph has a Hamiltonian Path is NP-complete.</p>

<p>Edited to add: Call a path that is allowed to revisit nodes a <em>walk</em>. 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.</p>

CC BY-SA 3.0
2011-08-04T00:03:42.793Z
OP is not looking for a Hamiltonian Path but for a path that contains all vertices (i.e. vertices can be reused).
Tyson Williams
CC BY-SA 3.0
2011-08-04T00:11:49.947Z
From what I understand of Hamiltonian paths, they have to visit each vertex exactly once. But I allow to revisit edges and nodes. So I believe it isn't NP-Complete.
Veehmot
CC BY-SA 3.0
2011-08-04T00:59:44.430Z
Nice answer.  Nitpicking: “weight n” should be “weight n−1.”
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-04T01:34:40.297Z
@Tsuyoshi Ito: You are correct. I'll fix it.
mhum
CC BY-SA 3.0
2011-08-04T03:04:27.753Z
So there's no efficient solution?
Veehmot
CC BY-SA 3.0
2011-08-04T05:37:24.207Z
@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.
Andrej Bauer
CC BY-SA 3.0
2011-08-04T05:45:43.490Z
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.)
Raphael
CC BY-SA 3.0
2011-08-04T18:06:35.303Z
True. However Veehmot's original question has indeed been answered by mhum.
Suresh Venkat
CC BY-SA 3.0
2011-08-04T23:21:44.147Z
@Veehmot: A more correct statement is "there is no **known** efficient solution".
Fixee
CC BY-SA 3.0
2011-08-04T23:55:32.323Z
@Veehmot: It's entirely possible there *is* an algorithm that efficiently solves your problem for all inputs you care about; mhum's proof says essentially that "if your graph has all degrees = 4, then some graphs of this form have no known efficient solution."  Your graphs are max degree 4, not necessarily 4-regular.  In fact, if your inputs cannot be 4-regular, the proof doesn't even apply.  (It's easy to see that for inputs with max-degree = 2, a solution is straightforward in fact.)
Fixee
CC BY-SA 3.0
2011-08-05T03:27:39.240Z
Thanks all for your time. I resolved using Kruskal algorithm.
Veehmot
CC BY-SA 3.0
2011-08-05T04:14:19.330Z
Not sure what "resolved" means in this case.
Suresh Venkat
CC BY-SA 3.0
2011-08-03T23:51:58.637Z
2011-08-04T01:34:50.420Z
2011-08-04T01:34:50.420Z
mhum
<p><strong>Update:</strong></p>
<p>This is my solution with Kruskal's Algorithm, although it doesn't take into account real &quot;path&quot;. Brute force may be the only solution.</p>
<p><a href="http://www.youtube.com/watch?v=VbSwwos4R2E" rel="nofollow noreferrer">http://www.youtube.com/watch?v=VbSwwos4R2E</a></p>
<p>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.</p>
<p><img src="https://i.sstatic.net/jBfFn.png" alt="Graph Example" /></p>
<p>I uploaded the graph drawing as an example. In that example, one good route would be:</p>
<blockquote>
<p>A - B - C - D - E - F - G - H - I - J - K - L - H - I - M</p>
</blockquote>
<p>Summing weights:</p>
<blockquote>
<p>11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 2 + 4 + 4 + 4 + 2 + 1 = <strong>61</strong></p>
</blockquote>
<p>But another route, with less weight, would be:</p>
<blockquote>
<p>A - B - C - D - E - F - G - H - I - M - I - H - L - K - J</p>
</blockquote>
<p>Weights:</p>
<blockquote>
<p>11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 1 + 1 + 2 + 4 + 4 + 4 = <strong>60</strong></p>
</blockquote>
<p>Of course, I want to get the path with less weight. Revisited is allowed because otherwise I can't visit all nodes.</p>
<p>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.</p>
<p>Thanks!</p>

CC BY-SA 3.0
2011-08-03T22:51:08.050Z
This is too basic to be suitable on cstheory.stackexchange.com, and it is a cross-post of http://math.stackexchange.com/questions/55221/need-an-efficient-algorithm-to-visit-all-nodes-of-a-graph-revisiting-edges-and-n.  Voted to close as off topic.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-03T23:21:34.543Z
Oops.  I may have voted to close too quickly.  If it is guaranteed that the input graph is [planar](http://en.wikipedia.org/wiki/Planar_graph), 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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-03T23:25:49.050Z
What kind of graph are you dealing with?
Mark
CC BY-SA 3.0
2011-08-03T23:30:21.977Z
Tsuyoshi: It is a cross-post, because Math.se redirected me here: "consider cross-posting your question to cstheory.SE; that community specializes in this kind of problem (among other things). – Fixee"
Veehmot
CC BY-SA 3.0
2011-08-03T23:35:17.107Z
@Mark: it is a connected undirected planar graph.
Veehmot
CC BY-SA 3.0
2011-08-03T23:51:09.260Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-03T23:59:27.787Z
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?
Tyson Williams
CC BY-SA 3.0
2011-08-04T02:28:48.097Z
@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.)
Tsuyoshi Ito
<ds.algorithms><graph-algorithms><planar-graphs>
Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed
Veehmot
# Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

(Asked by: username_0 on 2011-08-03)

**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](https://i.sstatic.net/jBfFn.png)

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!

**Tags:** ds.algorithms, graph-algorithms, planar-graphs
> **Comments:**
> **username_1**: This is too basic to be suitable on cstheory.stackexchange.com, and it is a cross-post of http://math.stackexchange.com/questions/55221/need-an-efficient-algorithm-to-visit-all-nodes-of-a-graph-revisiting-edges-and-n.  Voted to close as off topic.  
> **username_1**: Oops.  I may have voted to close too quickly.  If it is guaranteed that the input graph is [planar](http://en.wikipedia.org/wiki/Planar_graph), 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.  
> **username_2**: What kind of graph are you dealing with?  
> **username_0**: Tsuyoshi: It is a cross-post, because Math.se redirected me here: "consider cross-posting your question to cstheory.SE; that community specializes in this kind of problem (among other things). – Fixee"  
> **username_0**: @Mark: it is a connected undirected planar graph.  
> **username_1**: 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.  
> **username_3**: 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?  
> **username_1**: @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.)  

---

## 1 answers

### Answer by username_4 on 2011-08-03. Score: 14 | Accepted answer

According to [this abstract](http://www.sciencedirect.com/science/article/pii/0304397594901856), 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.

> **Comments:**
> **username_3**: OP is not looking for a Hamiltonian Path but for a path that contains all vertices (i.e. vertices can be reused).  
> **username_0**: From what I understand of Hamiltonian paths, they have to visit each vertex exactly once. But I allow to revisit edges and nodes. So I believe it isn't NP-Complete.  
> **username_1**: Nice answer.  Nitpicking: “weight n” should be “weight n−1.”  
> **username_4**: @Tsuyoshi Ito: You are correct. I'll fix it.  
> **username_0**: So there's no efficient solution?  
> **username_5**: @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.  
> **username_6**: 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.)  
> **username_7**: True. However Veehmot's original question has indeed been answered by mhum.  
> **username_8**: @Veehmot: A more correct statement is "there is no **known** efficient solution".  
> **username_8**: @Veehmot: It's entirely possible there *is* an algorithm that efficiently solves your problem for all inputs you care about; mhum's proof says essentially that "if your graph has all degrees = 4, then some graphs of this form have no known efficient solution."  Your graphs are max degree 4, not necessarily 4-regular.  In fact, if your inputs cannot be 4-regular, the proof doesn't even apply.  (It's easy to see that for inputs with max-degree = 2, a solution is straightforward in fact.)  
> **username_0**: Thanks all for your time. I resolved using Kruskal algorithm.  
> **username_7**: Not sure what "resolved" means in this case.  

---

