This problem is NP-complete, which can be proved by a reduction from the problem $3$-SAT.
Let the input of a $3$-SAT instance be
$n$ boolean variables, namely, $x_1$, $x_2$, $\cdots$, $x_n$
$m$ clauses of the form $l_1 \lor l_2 \lor l_3$, where each literal $l_i$ is either $x_j$ or $\neg x_j$ for some $1 \leq j \leq n$
We construct an instance of your problem from the $3$-SAT instance such that there exists a path in your problem if and only if the $3$-SAT instance is satisfiable.
$\blacksquare\ $ We first construct a directed graph $G$ as follows:
For each clause $c_j = l_{j,1} \lor l_{j,2} \lor l_{j,3}$, we create $3$ vertices which correspond to $l_{j,1}$, $l_{j,2}$, and $l_{j,3}$ respectively. We also create a vertex $u_j$ representing the clause $c_j$ itself. For example, given a clause $x_1 \lor \neg x_2 \lor x_3$, we will create $3$ vertices representing $x_1$, $\neg x_2$, and $x_3$.
For each clause $c_j = l_{j,1} \lor l_{j,2} \lor l_{j,3}$, create a directed edge from the vertex representing $l_{j,1}$ to the vertex $u_j$ which represents $c_j$. For example, given a clause $c_j = x_1 \lor \neg x_2 \lor x_3$, directed edges $(x_1, u_j)$, $(\neg x_2, u_j)$ and $(x_3, u_j)$ will be created.
For $1 \leq j < m$, we create a directed edge from $u_j$ to the vertex representing $l_{j+1,i}$ for $1 \leq i \leq 3$; that is, we create edges so that we can go from the $j$-th clause to the $(j + 1)$-th clause.
Additionally, we create two another vertices $v$ and $w$. We create a directed edge from $v$ to the vertex representing $l_{1,i}$ for $1 \leq i \leq 3$ and a directed edge from $u_m$ to $w$.
$\blacksquare\ $ We next construct the constraint pairs as follows:
- For each boolean variable $x_i$, let $V_i$ denote the vertices in $G$ that represents the literal $x_i$ and $V'_i$ denote those representing $\neg x_i$. For each $v' \in V_i$ and $w' \in V'_i$, we create a constraint pair $(v', w')$.
Note: this construction is polynomial.
Proof: Obviously, your problem is in the class NP. We prove below that there exists a path from $v$ to $w$ in the graph $G$ constructed without violating the constraints if and only if the $3$-SAT instance is satisfiable.
$\Leftarrow$ Part: If $3$-SAT is satisfiable, for each $c_j = l_{j,1} \lor l_{j,2} \lor l_{j,3}$, at least one of $l_{j,1}$, $l_{j,2}$ and $l_{j,3}$ is evaluated as true. Without loss of generality, suppose $l_{j,1}$ is the one that is true and let the vertex representing $l_{j,1}$ be $u_{j,1}$. We can see that the path
$$
\mathcal{P} = v \rightarrow u_{1,1} \rightarrow u_1 \rightarrow u_{2,1} \rightarrow u_2 \rightarrow \cdots \rightarrow u_{m,1} \rightarrow u_m \rightarrow w
$$
does not violate any constraint pair.
$\Rightarrow$ Part: Suppose we have a path $\mathcal{P}$ from $v$ to $w$ in $G$ without violating any constraint pair. Then one of $3$ vertices for each clause $c_j$ is visited. Without loss of generality, let the vertex be $u_{j,1}$ and its corresponding literal is $l_{j,1}$. If $l_{j,1} = x_i$, we then set $x_i$ as true; otherwise if $l_{j,1} = \neg x_i$, we set $x_i$ as false. The resulting truth assignment to $x_i$s satisfies the $3$-SAT.
