- INSTANCE:
Graph
.
- SOLUTION:
Simple path in
*G*, i.e., a sequence of distinct vertices such that, for any , . - MEASURE:
Length of the path, i.e., the number of edges in the path.

*Good News:*Approximable within [13].*Bad News:*Not in APX [289].*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].

*Garey and Johnson:*ND29