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.

$\endgroup$
3
  • $\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$ Commented Dec 26, 2014 at 23:16
  • 1
    $\begingroup$ You mention TSP: is your graph weighted? If so, the question should say so. $\endgroup$ Commented Dec 27, 2014 at 0:27
  • $\begingroup$ I have Edited it. $\endgroup$ Commented Dec 27, 2014 at 22:02

1 Answer 1

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.

$\endgroup$
4
  • $\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$ Commented Dec 27, 2014 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$ Commented Dec 27, 2014 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$ Commented Dec 28, 2014 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$ Commented Dec 28, 2014 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.