Next: SHORTEST WEIGHT-CONSTRAINED PATH Up: Routing Problems Previous: MINIMUM GENERAL ROUTING Index

### LONGEST PATH

- 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 [14].

- Bad News: Not in APX [274].

- 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 [274]. Similar results hold for a chromatic version of the problem [62]. 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.

- Garey and Johnson: ND29