Search

Given a graph G=(V,E), two fixed vertices s,[email protected]?V and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs. We write [email protected]?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)@?F we have [email protected]?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)@?F satisfy [email protected]?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)@?F satisfy [email protected][email protected][email protected]?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.