How many edges are cut in a balanced partition of a graph?

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?

• 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. – Konstantinos Koiliaris Jun 30 '15 at 15:36
• You are right on that. I have clarified the question – fokatsar Jun 30 '15 at 21:38

1 Answer

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.