On the complexity of paths avoiding forbidden pairs Original Research Article

Given a graph image, two fixed vertices image and a set image of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from image to image that contains at most one vertex from each pair in image. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in image. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.