# Shortest cycle with a specific number of vertices

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?

• 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." Oct 25, 2012 at 2:15
• That's exactly what I mean, thank you, I'll edit it now. Oct 25, 2012 at 15:39
• This sounds like a generalization of TSP Oct 25, 2012 at 16:22
• 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. Nov 15, 2012 at 16:28
• 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. Nov 26, 2012 at 4:37

• 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/…. Oct 26, 2012 at 15:49