Next: SHORTEST PATH WITH FORBIDDEN
Up: Miscellaneous
Previous: Miscellaneous
  Index
- INSTANCE:
Graph
and a collection
of pairs of vertices from V.
- SOLUTION:
A simple path in G that contains at most one vertex from each pair in C.
- MEASURE:
Length of the path, i.e., the number of edges in the path.
- Bad News:
NPO PB-complete [77].
- Comment:
Transformation from LONGEST COMPUTATION.
- Garey and Johnson: GT54
Viggo Kann
2000-03-20