LONGEST PATH WITH FORBIDDEN PAIRS

Next: SHORTEST PATH WITH FORBIDDEN Up: Miscellaneous Previous: Miscellaneous Index

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

Viggo Kann
2000-03-20