- 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 [284].*Comment:*Transformation from SHORTEST COMPUTATION.