SHORTEST PATH WITH FORBIDDEN PAIRS

• 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.