NP-Complete Reduction

Question

Prove the following problem is NP-Complete:
The problem gave a directed graph G, and several subsets of vertices of such graph are being specified as T1,T2,....Tn, and the subsects could intersect, does there exist a path in G where it doesn't contain any cycle and for every subsect Ti, the path consist of exactly 3 vertices from Ti?

On the proving part I've found the certificate to verify such problem but I'm stuck on the reduction process and cannot think of a previously-exist NP-Complete problem to reduced to, I've thought of TSP, Dir-Ham Cycle and even 3SAT,For the TSP I've though about picking vertices from each subset and form a map based on such, if there exist a specific combination of vertices along with a path resulting a specific value then we can say yes to the question, however that's a bit brutal force rather than polynomial, but TSP in my perspective is the most reasonable for this condition, I've though about dir ham-cycle but the intuition still falls apart, may I please get some assist on what direction should I approach it with?

Answer 1

I think a reduction from $\texttt{Directed Hamiltonian Path}$ (not cycle) would work quite well.

Given a digraph $G = (V, E)$ where $V = \{v_1, …, v_n\}$, consider the digraph $G' = (V', E')$ where:

• for all $i \in \{1, …, n\}$, $T_i = \{v_{i,1}, v_{i,2}, v_{i,3}\}$;

• $V'$ consist of three copies of each vertex $v_i$: $\bigcup\limits_{i=1}^n T_i$;

• $E' = \{(v_{i,3}, v_{j,1})\mid (v_i, v_j)\in E\} \cup \bigcup\limits_{i=1}^n\{(v_{i,1}, v_{i,2}), (v_{i,2}, v_{i,3})\}$, meaning that for each edge $v_i\rightarrow v_j$, you create $v_{i,3}\rightarrow v_{j,1}$, and for each vertex $v_i$, you create a path $v_{i,1}\rightarrow v_{i,2}\rightarrow v_{i,3}$.

It is clear that this construction can be done in polynomial time in the size of $G$.

Now, $G$ has a Hamiltonian path if and only if there is an acyclic path in $G'$ containing exactly $3$ vertices from each $T_i$. Can you see why?