# Minimum cost path connecting exactly K vertices

I came across a situation in real life that maps to this optimization problem:

Given a fully connected, undirected, weighted graph with $$N \ge K$$ vertices, find the simple path connecting exactly $$K$$ vertices with the minimum cost1

My understanding is that when $$K=N$$ this is the Traveling Salesman Problem. I was initially expecting to find a best approach in the literature, but despite my efforts I was unable to.

Generally for this problem $$N \sim 10^2$$. Ideally I would like:

• An exact solution2, if $$K \ll N$$
• A good approximation otherwise

I would need my own implementation. Which algorithms / heuristics should I be looking at?

1. Intended as sum of weights on the edges

2. I believe Held-Karp would work for this, but I'm not sure whether there are better approaches I'm not aware of.

• I assume you've looked at the Wikipedia page on the TSP, including algorithms based on ILP?
– D.W.
Commented May 27 at 21:02
• What's your definition for "fully connected" ?
– JimN
Commented May 27 at 21:19
• @JimN, there is an edge between every pair of vertices. Commented May 27 at 21:21
• @D.W., Yes, I had looked into that early on, then went on many tangents while researching, I'll review it now. ILP is not a field I'm very familiar with. I have two main concerns: first, I am not sure I understand how to extend the full formulation to my subproblem for non-DP algorithms like Held-Karp; second, I know there exist multiple industrial grade solvers for ILP problems using algorithms like simplex / branch & bound + advanced heuristics, but I'm not sure how well a naïve implementation would do, and I'm not sure how to formulate the problem in OR terms. Commented May 27 at 21:43
• There is a 2-approximation for this problem. The problem is known as $k$-TSP, or sometimes Quota TSP, and is a variant of the prize-collecting TSP; specifically when the prize is unit and the penalty is set to 0. Commented May 27 at 21:51