<p>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.</p>

CC BY-SA 3.0
2012-10-26T07:31:46.300Z
I think you mean Euclidian case can be approximated in constant factor? in the general case it should be APX-Hard like TSP.
Saeed
CC BY-SA 3.0
2012-10-26T15:19:32.447Z
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
CC BY-SA 3.0
2012-10-26T15:49:21.813Z
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 http://dl.acm.org/citation.cfm?id=1060650. For asymmetric distances that satisfy triangle inequality, an $O(\log^3 k)$ is known from http://www.cs.illinois.edu/homes/chekuri/papers/orienteering-journal.pdf and an $O(\log^2 n \log k/\log \log n)$ result from http://researcher.watson.ibm.com/researcher/files/us-viswanath/dir-orient.pdf.
Chandra Chekuri
CC BY-SA 3.0
2012-10-25T20:14:34.870Z
2012-10-25T20:14:34.870Z
David Eppstein
<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-10-25T02:15:10.940Z
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
CC BY-SA 3.0
2012-10-25T15:39:49.743Z
That's exactly what I mean, thank you, I'll edit it now.
rptynan
CC BY-SA 3.0
2012-10-25T16:22:00.970Z
This sounds like a generalization of TSP
Suresh Venkat
CC BY-SA 3.0
2012-11-15T16:28:34.287Z
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
CC BY-SA 3.0
2012-11-26T04:37:59.907Z
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
CC BY-SA 3.0
2012-12-02T00:05:43.400Z
Unfortunately that's not the case, vertices can only be visited once.
rptynan
<ds.algorithms><graph-theory><graph-algorithms><tsp>
Shortest cycle with a specific number of vertices
rptynan
# Shortest cycle with a specific number of vertices

(Asked by: username_0 on 2012-10-24)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, tsp
> **Comments:**
> **username_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."  
> **username_0**: That's exactly what I mean, thank you, I'll edit it now.  
> **username_2**: This sounds like a generalization of TSP  
> **username_3**: 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.  
> **username_4**: 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.  
> **username_0**: Unfortunately that's not the case, vertices can only be visited once.  

---

## 1 answers

### Answer by username_5 on 2012-10-25. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_6**: I think you mean Euclidian case can be approximated in constant factor? in the general case it should be APX-Hard like TSP.  
> **username_5**: 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.  
> **username_7**: 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 http://dl.acm.org/citation.cfm?id=1060650. For asymmetric distances that satisfy triangle inequality, an $O(\log^3 k)$ is known from http://www.cs.illinois.edu/homes/chekuri/papers/orienteering-journal.pdf and an $O(\log^2 n \log k/\log \log n)$ result from http://researcher.watson.ibm.com/researcher/files/us-viswanath/dir-orient.pdf.  

---

