enter image description here

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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.