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?
2
-
2$\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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
One such problem is maximum agreement correlation clustering as discussed by Swamy (2004). For general weighted graphs, this problem is APX-hard (Charikar, Guruswami and Wirth 2005). For unweighted complete graphs, there exists a PTAS (Bansal, Blum and Chawla 2004).
