# Directed Acyclic Graph partition into minimum subgraphs with a constraint

I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 constraints:-

1. A sub-graph should have nodes of similar color
2. A sub-graph cannot directly or indirectly depend on it's own output

Example:- In the attached picture, the sub-graph with yellow nodes is invalid since input from the red node breaks rule#2 : 4th node from top has an input which depends on output of 2nd node - via the red node (outside the sub-graph) Hence the algorithm should partition it after #2 or #3 so that 2 and 4 are on different sub-graphs

Am sure this is a pretty common problem in Graph theory and must have a name and a standard algorithm for it. Thanks in advance for any pointers to it!

• How about partition the whole graph into one subgraph? – John L. Jul 27 '19 at 4:13
• Or did you mean to partition the graph into sub-forest? – John L. Jul 27 '19 at 19:20