0
$\begingroup$

Given a Directed Graph G, and some subsets of vertices T1,T2,..Tn(These subset can intersect) , is there a path in this graph such that it is acyclic and contains exactly 3 vertices from each Ti. I'm not sure , but I have an intuition that this is a problem that can be reduced from hamiltonian path problem , just can't figure out how to reduce it . Because in HAM-Path all vertices have to be visited , in this question though all vertices need not be visited in the path.

$\endgroup$
2
  • $\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:25
  • $\begingroup$ This question appears to be identical to cs.stackexchange.com/q/155750/755. If it is not, please edit the question to make clear how this question is different. $\endgroup$
    – D.W.
    Commented Nov 28, 2022 at 19:26

0