Publication at Faculty of Mathematics and Physics |
2009
Abstract
Given a graph $G=(V,E)$, two fixed vertices $s,t\in V$ and a set $F$ of pairs of vertices (called {\em forbidden pairs}), the {\em 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.