ND39 L ONGEST P ATH

     
• I NSTANCE : Graph .
• S OLUTION : Simple path in G , i.e., a sequence of distinct vertices such that, for any , .
• M EASURE : Length of the path, i.e., the number of edges in the path.

• Good News: Approximable within [ 8 ].
• Bad News: Not in A PX [ 206 ].
• Comment: Transformation from M INIMUM M ETRIC T RAVELING S ALESPERSON P ROBLEM with distances one and two: A PX -hard and self-improvable. Not approximable within for any unless NP QP [ 206 ]. Similar results hold for a chromatic version of the problem [ 39 ]. Variation in which the path must be induced subgraph of G , L ONGEST I NDUCED P ATH , is NPO PB-complete and not approximable within for any , see M AXIMUM I NDUCED C ONNECTED S UBGRAPH WITH P ROPERTY P .
• Garey and Johnson: ND29