<p>There are no polynomial-time $\alpha$-approximation algorithms for <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow">TSP</a> where $\alpha$ is a constant unless $\mathsf{P} = \mathsf{NP}$. </p>

<p>However, for metric TSP there are approximation algorithms, e.g. <a href="https://en.wikipedia.org/wiki/Christofides_algorithm" rel="nofollow">Christofides algorithm</a>. A simpler 2-approximation is obtained by taking an <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow">MST</a>.</p>

CC BY-SA 3.0
2013-07-21T18:35:42.277Z
Are you sure this answers the OP's question?  He doesn't mention anything about the quality of a solution...just about the search version.  I suggest asking for clarification first.
Tyson Williams
CC BY-SA 3.0
2013-07-22T05:20:43.230Z
It's the OP's responsibility to pose the problem clearly enough that we can understand what he wants.  Given the vague query in the question, this is not an unreasonable answer; it's related, at least.
D.W.
CC BY-SA 3.0
2013-07-22T13:27:49.253Z
@D.W. And its the community's job to make sure the question was, in fact, clearly stated.
Tyson Williams
CC BY-SA 3.0
2013-07-23T14:45:39.857Z
@Tyson, you should ask the OP not me to clarify the question if you think it is not clear. I think the question was understandable from the motivation.
Kaveh
CC BY-SA 3.0
2013-07-23T21:40:59.720Z
Of course, but you already answered and I made this comment while on my phone, where it is very difficult to make both understandable and technically correct mathematical statements. Also, I don't see how you conclude that the OP is interested in minimizing distance given the motivation. You already admit in a comment to the question that you assumed the question is for undirected graphs. I am much more familiar with buses than subways, and they do take asymmetric routes. It is conceivable to me that some city has subways that only run in one direction in the morning and another at night.
Tyson Williams
CC BY-SA 3.0
2013-07-21T12:07:56.370Z
2013-07-21T12:07:56.370Z
Kaveh
<p>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.</p>

CC BY-SA 3.0
2013-07-21T22:56:14.577Z
It is always possible if the graph is connected.
Kaveh
CC BY-SA 3.0
2013-07-22T00:43:13.333Z
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
CC BY-SA 3.0
2013-07-22T01:15:45.710Z
Right, I was under the impression that it would be necessary to visit some vertices twice.
Liam M.
CC BY-SA 3.0
2013-07-22T08:00:23.623Z
@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
CC BY-SA 3.0
2013-07-23T13:50:22.150Z
**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ε
<graph-theory><co.combinatorics><optimization>
Finding Tours through Near-Hamiltonian Paths?
Liam M.
# Finding Tours through Near-Hamiltonian Paths?

(Asked by: username_0 on 2013-07-21)

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.

**Tags:** graph-theory, co.combinatorics, optimization

> **Comments:**
> **username_1**: It is always possible if the graph is connected.  
> **username_2**: Do you mean you are allowed to visit a vertex twice if necessary? @username_1 but if the graph is is directed then its not always possible even if its connected.  
> **username_0**: Right, I was under the impression that it would be necessary to visit some vertices twice.  
> **username_1**: @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.  
> **username_3**: **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?  

---

## 1 answers

### Answer by username_1 on 2013-07-21. Score: 0 | Accepted answer

There are no polynomial-time $\alpha$-approximation algorithms for [TSP](https://en.wikipedia.org/wiki/Travelling_salesman_problem) where $\alpha$ is a constant unless $\mathsf{P} = \mathsf{NP}$.

However, for metric TSP there are approximation algorithms, e.g. [Christofides algorithm](https://en.wikipedia.org/wiki/Christofides_algorithm). A simpler 2-approximation is obtained by taking an [MST](https://en.wikipedia.org/wiki/Minimum_spanning_tree).

> **Comments:**
> **username_4**: Are you sure this answers the OP's question?  He doesn't mention anything about the quality of a solution...just about the search version.  I suggest asking for clarification first.  
> **username_5**: It's the OP's responsibility to pose the problem clearly enough that we can understand what he wants.  Given the vague query in the question, this is not an unreasonable answer; it's related, at least.  
> **username_4**: @username_5 And its the community's job to make sure the question was, in fact, clearly stated.  
> **username_1**: @Tyson, you should ask the OP not me to clarify the question if you think it is not clear. I think the question was understandable from the motivation.  
> **username_4**: Of course, but you already answered and I made this comment while on my phone, where it is very difficult to make both understandable and technically correct mathematical statements. Also, I don't see how you conclude that the OP is interested in minimizing distance given the motivation. You already admit in a comment to the question that you assumed the question is for undirected graphs. I am much more familiar with buses than subways, and they do take asymmetric routes. It is conceivable to me that some city has subways that only run in one direction in the morning and another at night.  

---

