0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is always possible if the graph is connected. $\endgroup$ – Kaveh Jul 21 '13 at 22:56
  • $\begingroup$ 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. $\endgroup$ – Pratik Deoghare Jul 22 '13 at 0:43
  • $\begingroup$ Right, I was under the impression that it would be necessary to visit some vertices twice. $\endgroup$ – Liam M. Jul 22 '13 at 1:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Kaveh Jul 22 '13 at 8:00
  • 1
    $\begingroup$ 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? $\endgroup$ – Jeffε Jul 23 '13 at 13:50
0
$\begingroup$

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

However, for metric TSP there are approximation algorithms, e.g. Christofides algorithm. A simpler 2-approximation is obtained by taking an MST.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tyson Williams Jul 21 '13 at 18:35
  • $\begingroup$ 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. $\endgroup$ – D.W. Jul 22 '13 at 5:20
  • 1
    $\begingroup$ @D.W. And its the community's job to make sure the question was, in fact, clearly stated. $\endgroup$ – Tyson Williams Jul 22 '13 at 13:27
  • $\begingroup$ @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. $\endgroup$ – Kaveh Jul 23 '13 at 14:45
  • $\begingroup$ 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. $\endgroup$ – Tyson Williams Jul 23 '13 at 21:40

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.