# Finding Tours through Near-Hamiltonian Paths?

Say I have a connected graph. I want to find a tour that visits each vertex at least once. It's not always possible, though, for there to be a solution if there is a bridge in the graph. Is there a term for this sort of problem or a recommended approach to solving it? The motivation if it helps that I ultimately have in mind is traversing every station in a subway system.

• It is always possible if the graph is connected. – Kaveh Jul 21 '13 at 22:56
• Do you mean you are allowed to visit a vertex twice if necessary? @Kaveh but if the graph is is directed then its not always possible even if its connected. – Pratik Deoghare Jul 22 '13 at 0:43
• Right, I was under the impression that it would be necessary to visit some vertices twice. – Liam M. Jul 22 '13 at 1:15
• @Pratik, the question didn't mention "directed graphs" so I assume it is not. If the graph is directed then OP should explain what does being connected mean. If it is strongly connected then the situation is similar. – Kaveh Jul 22 '13 at 8:00
• Please clarify the question. What exactly is a "tour"? Can tours visit vertices more than once? Can they traverse edges more than once? Must they start and end at the same vertex? Are your graphs directed or undirected? – Jeffε Jul 23 '13 at 13:50

There are no polynomial-time $\alpha$-approximation algorithms for TSP where $\alpha$ is a constant unless $\mathsf{P} = \mathsf{NP}$.