# NP-Complete Reduction

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?

• What's the context where you encountered this problem? Can you credit the original source where you saw it? What's the motivation?
– D.W.
Nov 28, 2022 at 19:27

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?