5
$\begingroup$

Given an undirected graph with n nodes, I need to find the shortest cycle of involving exactly n/2 vertices (i.e. keeping the distance traveled by the cycle to a minimum). Some nodes cannot directly connect; they're in specific areas and I can only travel from one area to another, not within one area.

I'm just asking in general here, what kind of techniques can I use to get the best (shortest) possible cycle of n/2 nodes? So far I've written a basic substitution optimizer and just a greedy Depth First Search. I'm wondering what would be the best approach for me to start on now?

$\endgroup$
6
  • 1
    $\begingroup$ It seems you are using "length/distance" in two different ways. If I understand correctly, I would say that you are looking for "the shortest cycle that involves exactly 40 vertices." $\endgroup$ Oct 25, 2012 at 2:15
  • $\begingroup$ That's exactly what I mean, thank you, I'll edit it now. $\endgroup$
    – rptynan
    Oct 25, 2012 at 15:39
  • 2
    $\begingroup$ This sounds like a generalization of TSP $\endgroup$ Oct 25, 2012 at 16:22
  • $\begingroup$ You should make the question general, 80 and 40 should be replaced by n and n/2. Are you sure there exists a cycle of length at least n/2? Because in general finding the longest cycle is a very hard question. $\endgroup$ Nov 15, 2012 at 16:28
  • $\begingroup$ Note that if you don't require the cycle to be simple (the cycle can repeat edges and vertices, and you count edges with multiplicity), then you can solve this with fairly standard dynamic-programming algorithms. $\endgroup$
    – Neal Young
    Nov 26, 2012 at 4:37

1 Answer 1

15
$\begingroup$

The problem of finding the shortest tour that covers a given number k of nodes is usually referred to as k-TSP. Searching Google scholar for that term will find some relevant literature. It is NP-hard but can be approximated within a constant factor. So finding an exact solution may be out of reach, unless you're prepared to use sophisticated branch and bound methods extending what Concorde does for the usual TSP.

$\endgroup$
3
  • 1
    $\begingroup$ I think you mean Euclidian case can be approximated in constant factor? in the general case it should be APX-Hard like TSP. $\endgroup$
    – Saeed
    Oct 26, 2012 at 7:31
  • 1
    $\begingroup$ The arbitrary metric case also has a constant approximation: see e.g. Arora and Karakostas SODA 2000. I guess if you have asymmetric distances or no triangle inequality then it should be harder to approximate, though. $\endgroup$ Oct 26, 2012 at 15:19
  • 5
    $\begingroup$ Constant factor for k-TSP applies only for metric graphs. Otherwise the problem is not approximable via TSP. For metric k-TSP there is a $2$-approximation due to Naveen Garg dl.acm.org/citation.cfm?id=1060650. For asymmetric distances that satisfy triangle inequality, an $O(\log^3 k)$ is known from cs.illinois.edu/homes/chekuri/papers/orienteering-journal.pdf and an $O(\log^2 n \log k/\log \log n)$ result from researcher.watson.ibm.com/researcher/files/us-viswanath/…. $\endgroup$ Oct 26, 2012 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.