0
$\begingroup$

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

New contributor
user145024 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
5
  • 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 at 19:49
  • 1
    $\begingroup$ I'm sure I've seen this question before here ... $\endgroup$
    – Pål GD
    Nov 24 at 20:44
  • $\begingroup$ This question seems to have been re-posted. $\endgroup$
    – nir shahar
    Nov 24 at 21:23
  • $\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 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 at 2:32

Your Answer

user145024 is a new contributor. Be nice, and check out our Code of Conduct.

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.