1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.