I have a DAG graph which contains two types of nodes, A and B.
I am looking for a graph partitioning algorithm that can partition a graph in sub-graphs such that each sub-graph contains up to X number of node type B. For example, given this graph, I need to partition it topologically such that each sub-graph contains up to 3 of node type B. I want to minimize the number of partitions. So I always try to have 3 blue nodes in each partition.
Would hypergraph partitioning be suitable for this and assign each blue node a weight (for example 1) and say each partition have a maximum weight of 3?
The solution to this would look like this graph which has been partitioned to 3 sub-graph each containing up to 3 of node type B.