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?
-
3$\begingroup$ 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. $\endgroup$– Neal YoungNov 21, 2022 at 14:26
-
$\begingroup$ 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. $\endgroup$– ZhudaFeb 1 at 9:33