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.
On
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
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.