Transformation from MINIMUM METRIC TRAVELING SALESPERSON PROBLEM with distances one and two: APX-hard and
Not approximable within
unless NPQP .
Similar results hold for a chromatic version of the problem
Variation in which the path must be induced subgraph of G,
LONGEST INDUCED PATH, is NPO PB-complete and not approximable within
see MAXIMUM INDUCED CONNECTED
SUBGRAPH WITH PROPERTY P.
Remains APX-hard even if restricted to dense instances .