1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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 Young
    Nov 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$
    – Zhuda
    Feb 1 at 9:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.