# Partial TSP in Euclidian plane

I'm interested in the following variant of Travelling Salesman Problem sometimes called Partial TSP. I'm particulary interested in the euclidian version :

Input : A set $\{x_1,\dots,x_n\}\subset \mathbb{R}^2$ of $n$ points in the plane, and an integer $k\le n$.

Output : A tour of $k$ points $x_{i_1},\dots, x_{i_k}$

Minimize : The length of the tour.

Is there any PTAS for this problem, or APX-hardness results ? Does Arora's technique applies on this case ?

• In general, Partial TSP is as hard as TSP (since when $k = n$ you get TSP). – Juho Jun 10 '18 at 14:35
• I'd rather say that Partial TSP is harder than TSP since it's a more general problem. I'd like to find a case where this problem is "striclty" harder – Mathieu Mari Jun 11 '18 at 15:09