Proving NP completeness of a graph problem

Question

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 vertices from each pair. Prove that this problem is NP-complete or give a polynomial algorithm.

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 is a polynomial. But I'm still not sure whether this algorithm is correct. Can anyone help?

Answer 1

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.