2
$\begingroup$

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:

enter image description here

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

Thanks!

|cite|improve this question
$\endgroup$
  • $\begingroup$ It seems like this problem is similar to the route inspection problem with the modification that you are interested in exploring all the vertices instead of all the edges. However there does not seem to be a way to reduce this problem to it. $\endgroup$ – Kaya Jul 14 '13 at 5:17
  • $\begingroup$ What is a minimum distance closed walk? $\endgroup$ – A.Schulz Jul 14 '13 at 8:03
  • $\begingroup$ I meant minimum cost, updated the question. $\endgroup$ – simonzack Jul 14 '13 at 8:12
  • 2
    $\begingroup$ cstheory "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" $\endgroup$ – Hendrik Jan Jul 14 '13 at 17:26
3
$\begingroup$

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.

enter image description here

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Can you elaborate a bit more on the converse, i.e. how does this reduce from TSP? $\endgroup$ – simonzack Jul 14 '13 at 10:23
  • $\begingroup$ I don't see the logic, since $K_n$ is arbitrary, why does replacing edge costs with shortest path costs not change the tour? $\endgroup$ – simonzack Jul 15 '13 at 11:00
2
$\begingroup$

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.

|cite|improve this answer
$\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.