- 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 [77].*Comment:*Transformation from LONGEST COMPUTATION.*Garey and Johnson:*GT54