Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite
1

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?

share|improve this question
1  
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
2  
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

1 Answer

up vote 14 down vote accepted

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.

share|improve this answer
Thanks, this exactly what I need. – rptynan Oct 25 '12 at 22:47
1  
I think you mean Euclidian case can be approximated in constant factor? in the general case it should be APX-Hard like TSP. – Saeed Oct 26 '12 at 7:31
1  
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. – David Eppstein Oct 26 '12 at 15:19
5  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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