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.
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. ♦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. ♦Nov 28, 2022 at 19:26
Add a comment
|