# 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." –  Tyson Williams Oct 25 '12 at 2:15
That's exactly what I mean, thank you, I'll edit it now. –  rptynan Oct 25 '12 at 15:39
This sounds like a generalization of TSP –  Suresh Venkat Oct 25 '12 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. –  Martin Vatshelle Nov 15 '12 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. –  Neal Young Nov 26 '12 at 4:37
show 1 more comment

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/…. –  Chandra Chekuri Oct 26 '12 at 15:49