Proving NP completeness of a graph problem Given a directed graph $G(V,E)$, vertexes $v, w$ and a list of pairs of vertexes $P$:
$$
P = (v_1, w_1), (v_2, w_2), \ldots, (v_k, w_k)
$$
The problem is to find a path between $v$ and $w$ which contains no more than one of vertexes from each pair.
Prove that this problem is NP-complete or give a polynomial algorhythm. 
I have an idea of using dfs with a disjoint set union (DSU) to solve this problem: first we unite vertexes from each pair, other vertexes unite in a one vertex set. Then we can colour each set in a unique colour. After that we have to find a path between $v$ and $w$ which does not contain two vertexes in one colour. This path can be found with dfs. This algorithm can is polynomial. But I'm still not sure whether this algorhithm is correct. Can anyone help?
 A: 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.
