Next: SHORTEST WEIGHT-CONSTRAINED PATH
Up: Routing Problems
Previous: MINIMUM GENERAL ROUTING
  Index
- 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 NP
QP [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
Viggo Kann
1999-04-22