1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I think TSP (with the constraint you point out that each vertex can be visited only once) would reduce to your problem. This would imply your problem is NP-hard. $\endgroup$ – James Evans Dec 26 '14 at 23:16
  • 1
    $\begingroup$ You mention TSP: is your graph weighted? If so, the question should say so. $\endgroup$ – David Richerby Dec 27 '14 at 0:27
  • $\begingroup$ I have Edited it. $\endgroup$ – bones.felipe Dec 27 '14 at 22:02
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What if the graph is weighted as David Richerby suggested? Indeed, the problem makes more sense if $G$ is weighted. I think in that case NP-hardness comes from the TSP problem, doesn't it? $\endgroup$ – Carlos Linares López Dec 27 '14 at 21:48
  • $\begingroup$ Indeed the graph is weighted, I've edited the question. But even if the graph is not weighted, how that reduction works?, in the sense of where is the K set of vertices of the original question? $\endgroup$ – bones.felipe Dec 27 '14 at 22:03
  • $\begingroup$ The set $K$ consists simply of all vertices. Allowing weights only makes the problem more difficult, so we might as well assume there are none. $\endgroup$ – Yuval Filmus Dec 28 '14 at 7:27
  • $\begingroup$ The weight constraint can be satisfied by getting the shortest distance between all the nodes in the Graph, then a new Graph $G'$ can be constructed like Yuval suggests and the weights must be the minimum that were found before, and it would be reduction from TSP. I think it would work that way. $\endgroup$ – bones.felipe Dec 28 '14 at 18:23

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.