# Partition a graph into subgraphs such that a partition contains up to X number of a particular node type

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.

• How is the topological partitionning relevant to your problem? Did I miss something? Also what is the constraint on the partition that stops you from creating subgraphs that contain any 3 type B nodes and any number of type B nodes? Nov 24, 2021 at 19:49
• I'm sure I've seen this question before here ... Nov 24, 2021 at 20:44
• This question seems to have been re-posted. Nov 24, 2021 at 21:23
• You deleted your prior post and re-posted it. Please don't do that. If you want to draw attention to your question, you can issue a bounty (once you have participated more). Re-posting loses the feedback and questions that were left in the comments. I see that last time someone asked a similar question: they asked what restrictions there are on the partitioning. I still don't see any specification of the restrictions on partitioning in this question; why can't we pick any group of 3 blue nodes and put them in their own partition?
– D.W.
Nov 25, 2021 at 2:31
• What does "partition it topologically" mean? Right now I don't see any way that the graph structure (the edges) influences which partitions are allowed. As such, I suspect you have not specified clearly all of your constraints. Please edit your question to clarify the problem.
– D.W.
Nov 25, 2021 at 2:32