Complexity of the path avoiding forbidden pairs problem revisited

Let G=(V,E)G=(V,E) be a directed acyclic graph with two distinguished vertices s,ts,t, and let FF be a set of forbidden pairs   of vertices. We say that a path in GG is safe  , if it contains at most one vertex from each pair {u,v}∈F{u,v}∈F. Given GG and FF, the path avoiding forbidden pairs   (PAFP) problem is to find a safe ss–tt path in GG.We systematically study the complexity of different special cases of the PAFP problem defined by the mutual positions of forbidden pairs. Fix one topological ordering ≺≺ of vertices; we say that pairs {u,v}{u,v} and {x,y}{x,y} are disjoint  , if u≺v≺x≺yu≺v≺x≺y, nested  , if u≺x≺y≺vu≺x≺y≺v, and halving  , if u≺x≺v≺yu≺x≺v≺y.The PAFP problem is known to be NP-hard in general or if no two pairs are disjoint; we prove that it remains NP-hard even when no two forbidden pairs are nested. On the other hand, if no two pairs are halving, the problem is known to be solvable in cubic time. We simplify and improve this result by showing an O(M(n))O(M(n)) time algorithm, where M(n)M(n) is the time to multiply two n×nn×n boolean matrices.