Next: MINIMUM POINT-TO-POINT CONNECTION Up: Miscellaneous Previous: LONGEST PATH WITH FORBIDDEN Index

### SHORTEST PATH WITH FORBIDDEN PAIRS

- INSTANCE: Graph , a collection of pairs of vertices from V, an initial vertex , and a final vertex .

- SOLUTION: A simple path from s to f 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 [269].

- Comment: Transformation from SHORTEST COMPUTATION.