3
$\begingroup$

Partition an undirected graph of $n$ nodes into $k$ subgraphs so that total vertices inside all subgraphs is maximum.

Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$); $k$ is given initially.

I'd like to receive pointers to the solution as well as papers or blogs related to or expanding on it.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ You might want to add the appropriate definitions to make sure we know what exact problem you are referring to. $\endgroup$ – dkaeae Feb 20 '19 at 9:28
  • $\begingroup$ Thank for pointing out. I've added the restriction. $\endgroup$ – Craneonacrane Feb 20 '19 at 9:48
  • $\begingroup$ You probably mean "total edges", not "total vertices". In any balanced partition, the total number of vertices in each part is always n/k. $\endgroup$ – Vincenzo Mar 22 '19 at 16:46
2
$\begingroup$

Your problem is a special case of graph partitioning. When $k=2$, the problem is known as minimum bisection, and is NP-complete.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.