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?

enter image description here

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.

enter image description here

  • 1
    $\begingroup$ 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? $\endgroup$
    – Nathaniel
    Nov 24, 2021 at 19:49
  • 1
    $\begingroup$ I'm sure I've seen this question before here ... $\endgroup$
    – Pål GD
    Nov 24, 2021 at 20:44
  • $\begingroup$ This question seems to have been re-posted. $\endgroup$
    – nir shahar
    Nov 24, 2021 at 21:23
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Nov 25, 2021 at 2:31
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Nov 25, 2021 at 2:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.