Next: SHORTEST PATH WITH FORBIDDEN Up: Miscellaneous Previous: Miscellaneous Index

### LONGEST PATH WITH FORBIDDEN PAIRS

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

- Comment: Transformation from LONGEST COMPUTATION.

- Garey and Johnson: GT54