Problem Detail: I have the following problem, I would like to know an efficient algorithm to solve it. Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex $s$ and visits at least once every vertex of $K$ such that the distance is minimized. There is no constraint on repeated nodes or edges in the walk found and is not guaranteed that the graph does not contain cycles. Some people have suggested me that it maybe NP-Hard due to a reduction from TSP, but there is no restriction of visit vertices exactly once, and is well known that TSP have that.
Asked By : bones.felipe
Answered By : Yuval Filmus
There is a simple reduction from Hamiltonian path. Suppose we are given a graph $G$ on $n$ vertices, and want to know whether it contains a Hamiltonian path. Adjoin a new vertex $s$ and connect it to all other vertices. The new graph $G’$ contains a walk of length (at most) $n$ starting at $s$ and covering all vertices if and only if the original graph $G$ contains a Hamiltonian path.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35687
