SHORTEST PATH WITH FORBIDDEN PAIRS

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

INSTANCE: Graph $G=\left(V,E\right)$ , a collection $C=\{(a_1,b_1),\ldots,(a_m,b_m)\}$ of pairs of vertices from V, an initial vertex $s\in V$ , and a final vertex $f\in V$ .
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 [284].
Comment: Transformation from SHORTEST COMPUTATION.

Viggo Kann
2000-03-20