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