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?
$\begingroup$
$\endgroup$
2
-
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$– Konstantinos KoiliarisCommented Jun 30, 2015 at 15:36
-
$\begingroup$ You are right on that. I have clarified the question $\endgroup$– fokatsarCommented Jun 30, 2015 at 21:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jul 8, 2015 at 23:41