[Math] The problem of finding the shortest path/route/tour that visits every vertex at least once

algorithmsgraph theory

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.

Best Answer

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.

Related Question