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 subgraph) Hence the algorithm should partition it after #2 or #3 so that 2 and 4 are on different nodes

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$ My best interpretation of what you wrote is (1) in each subgraph all nodes should be the same color, and (2) in each subgraph there should not be two nodes $u$ and $v$ such that there is a path from $u$ to $v$ in the original graph? But that doesn't seem consistent with your example, so I don't understand. Maybe you can state your problem more carefully, using just standard terminology? $\endgroup$ – Neal Young Aug 3 '19 at 3:18

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.