<p>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 <strong>minimum multisection</strong> (or partition): <em>Given a graph $G$ find a symmetric partition $P$ of its vertices such that it minimizes the edges between different clusters.</em></p>

<p>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].</p>

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

<p>[2] K. Andreev and H. Racke. Balanced graph partitioning. 2004.</p>

CC BY-SA 3.0
2015-07-08T23:41:41.823Z
2015-07-08T23:54:20.770Z
2015-07-08T23:54:20.770Z
Konstantinos Koiliaris
<p>Consider a graph on <em>n</em> nodes and <em>e</em> edges that is partitioned into <em>k</em> "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?</p>

CC BY-SA 3.0
2015-06-30T15:36:42.120Z
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
CC BY-SA 3.0
2015-06-30T21:38:23.717Z
You are right on that. I have clarified the question
fokatsar
<graph-theory><partition-problem>
How many edges are cut in a balanced partition of a graph?
fokatsar
# How many edges are cut in a balanced partition of a graph?

(Asked by: username_0 on 2015-06-30)

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?

**Tags:** graph-theory, partition-problem
> **Comments:**
> **username_1**: 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.  
> **username_0**: You are right on that. I have clarified the question  

---

## 1 answers

### Answer by username_1 on 2015-07-08. Score: 2

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.


---

