3
$\begingroup$

I have a non-directed non-weighted graph and I want to find the shortest path/route/tour (I don't know which is the correct definition) that visits every vertex at least once.

Is there an algorithm for this or a specific name about this kind of problem?

I know about traveling salesman problem but I don't have the restriction to visit each vertex exactly once nor to go back to the start.

$\endgroup$
1
$\begingroup$

I'm not sure if there is an exact name for this, but this problem is certainly NP hard. We see that the absolute shortest possible way to do this is to visit each vertex exactly once, which is precisely the Hamiltonian Path problem, which is known to be NP complete. Hence, your problem is going to be in NP, as if the shortest is everything exactly once, we have solved Hamiltonian Path.

$\endgroup$
  • $\begingroup$ I am going to read about hamiltonian path problem as soon as possibl but let's say i have this graph: B-C | | A-D-E | | G-F I can't visit each vertex exactly once. The optimal solution would be ABCDEDFG. $\endgroup$ – user16071 Jun 21 '14 at 20:59
  • $\begingroup$ Sure. I'm just saying that you know you can't do better than everything exactly once. So we can use your algorithm to solve Hamilton path simply by checking if the shortest walk is one which touches every vertex exactly once. $\endgroup$ – gregkow Jun 21 '14 at 21:10
  • $\begingroup$ I don't think that you can reduce this problem to the Hamiltonian path problem. In fact, one property of the Hamiltonian path problem that makes that problem so difficult is that you are only forced to visit each node exactly once. Relaxing this constraint might make the problem easier. I am not sure it remains and NP hard problem, though. $\endgroup$ – philipph Jul 14 '14 at 13:02
  • $\begingroup$ @philipph: Consider we have an algorithm Q that finds the shortest path touching all vertices at least once (not exactly once). Note: 1) For any graph, a path visiting all vertices obviously must be as long as the number of vertices, or greater. 2) If a graph has a Hamiltonian path, Q must return this path - any non-Hamiltonian path would have a higher cost. In this case, the path will have a length equal to the number of vertices, the shortest possible. [1/2] $\endgroup$ – GManNickG Nov 4 '17 at 6:26
  • $\begingroup$ 3) For any graph without a Hamiltonian path, Q will return a path of length greater than the number of vertices. If it could do better, than the graph would be Hamiltonian. 4) Therefore: given Q, we can then solve the Hamiltonian path problem by running Q on the graph and checking if the length of the resulting path is equal to the number of vertices. Since answering whether or not a graph has a Hamiltonian path is NP, Q must also be NP. [2/2] $\endgroup$ – GManNickG Nov 4 '17 at 6:26
0
$\begingroup$

I found that this problem has been studied by Dorzdowski et al. [1], in which they coined it as Mind The Gap (MTG) problem.

[1] Drozdowski, Maciej, et al. "Mind the gap: A study of Tube tour." Computers & Operations Research 39.11 (2012): 2705-2714. ftp://lamp.cfar.umd.edu/pub/liam/mind_the_gap.pdf

$\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.