# Graph partitioning to minimize sum of intra-partition edge weights

I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total sum of intra-partition edges (sum of edge weights within partitions themselves). I'm aware that it's np-hard, but do such algorithms exist, even approximations?

• Given graph with edge weights in $\{0,\infty\}$, the problem of determining whether there exists a 3-partition of the vertices that has cost zero by your metric (that is, uses only zero-weight edges within each cluster) is equivalent to the 3-COLOR problem (on the corresponding graph containing only the infinite-weight edges). So this problem cannot be approximated at all in polynomial time unless P=NP. Nov 21, 2022 at 14:26
• I was working on an engineering problem abour graph partitioning. Since I am not a CS major student, can you share some details about k-way partitioning. Feb 1 at 9:33