Minimum cost closed walk in a graph

Problem Detail: 

Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices?

Does this problem have a name? I tried to reduce this to similar problems (in particular the traveling salesman problem) to see if it was NP-hard, but was unsuccessful.

Here's an example:

Then a possible closed walk is: A,B,C,D,C,B,A, with a cost of 6.

Thanks!

Asked By : simonzack

Answered By : simonzack

Using this answer, by finding the minimum cost closed walk (or just it's cost) of an arbitrary 4-regular planar graph, with weights 1, we can decide whether it has a Hamiltonian Path, but this problem is NP-complete. So the original problem is NP-hard.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13267