LONGEST PATH WITH FORBIDDEN PAIRS

• INSTANCE: Graph $G=\left(V,E\right)$ and a collection $C=\{\left(a_1,b_1\right),\ldots,\left(a_m,b_m\right)\}$ 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