Minimum cost closed walk in a graph

Question

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!

Answer 1

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.

Answer 2

This problem is equivalent to TSP. Compute all pairwise shortest distances between the vertices in the given graph $G$. Then take the complete graph $K_n$ that is weighted with the shortest-distances of the original graph $G$. The TSP tour of the complete graph corresponds to the shortest min-cost closed walk.

More precisely, a shortest tour $\pi$ in $K_n$ decodes a closed walk in $G$: just replace every edge $(u,v)$ in $\pi$ by the shortest path from $u$ to $v$. Clearly, the costs are preserved. Assume that there would be a shorter closed walk in $G$. Select select the vertices in order they appear first. This permutation implies a tour in $K_n$ (maybe even shorter than the closed walk in $G$), hence we have a contradiction.

See the figure for your example.