On the complexity of paths avoiding forbidden pairs

Given a graph G=(V,E)G=(V,E), two fixed vertices s,t∈Vs,t∈V and a set FF of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs   is to find a path from ss to tt that contains at most one vertex from each pair in FF. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in PP. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.We write x≺yx≺y if and only if there exists a path from xx to yy and we assume, without loss of generality, that for every forbidden pair (x,y)∈F(x,y)∈F we have x≺yx≺y. The forbidden pairs have a halving structure   if no two pairs (u,v),(x,y)∈F(u,v),(x,y)∈F satisfy v≺xv≺x or v=xv=x and they have a hierarchical structure   if no two pairs (u,v),(x,y)∈F(u,v),(x,y)∈F satisfy u≺x≺v≺yu≺x≺v≺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.