# Graph partitioning with parts of equal size

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.

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

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