Next: SHORTEST PATH WITH FORBIDDEN
and a collection
of pairs of vertices from V.
A simple path in G that contains at most one vertex from each pair in C.
Length of the path, i.e., the number of edges in the path.
- Bad News:
NPO PB-complete .
Transformation from LONGEST COMPUTATION.
- Garey and Johnson: GT54