<p>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 <em>intra</em>-partition edges (sum of edge weights within partitions themselves). I'm aware that it's np-hard, but do such algorithms exist, even approximations?</p>

CC BY-SA 4.0
2022-11-21T14:26:04.103Z
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.
Neal Young
CC BY-SA 4.0
2023-02-01T09:33:56.297Z
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.
Zhuda
<graph-theory><partition-problem><clustering><minimization>
Graph partitioning to minimize sum of intra-partition edge weights
axizzt
# Graph partitioning to minimize sum of intra-partition edge weights

(Asked by: username_0 on 2022-11-21)

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?

**Tags:** graph-theory, partition-problem, clustering, minimization
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 0 answers

