Consider a graph on n nodes and e edges that is partitioned into k "balanced" subgraphs in the sense that each block has an equal number of nodes and the number of cut edges is minimized. Is there a formula for the number of cut edges in this situation?

  • 1
    $\begingroup$ Your question is not well defined. Graph partitioning algorithms are based on what you are trying to optimize. For example that could be the cut edges themselves. $\endgroup$ Jun 30, 2015 at 15:36
  • $\begingroup$ You are right on that. I have clarified the question $\endgroup$
    – fokatsar
    Jun 30, 2015 at 21:38

1 Answer 1


Even in the current updated version of the question, it still remains ill defined. There many different ways by which you can partition a graph into symmetric (or balanced if you like) clusters. One question that you might have in mind but have problem expressing is the minimum multisection (or partition): Given a graph $G$ find a symmetric partition $P$ of its vertices such that it minimizes the edges between different clusters.

In which case the answer is that the problem is NP-hard [1] and moreover it is NP-hard to approximate within a constant factor [2].

[1] L. Hyafil and R. L. Rivest. Graph partitioning and constructing optimal decision trees are polynomial complete problems. 1973.

[2] K. Andreev and H. Racke. Balanced graph partitioning. 2004.


Your Answer

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

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