Max-sum graph-partition for maximizing intra-edge weights?

Question

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.

Input: A graph G with negative or non-negative integer weights on edges.

Output: A partition $P=\{P_1, ..., P_K\}$ of $V(G)$

Measure (to maximize): The sum of the weights for the edges with both endpoints in the same set of P, i.e.:

$$ M(P)=\sum_{i=1}^k \sum_{u,v\in P_i} w\left( u,v \right) $$

where $w$ is the edge-weight function.

Thanks in advance for any suggestion.

Answer 1

I will consider the case of non-negative weights only. As I mentioned in the comment the problem is related to the minimum k-way cut problem where the goal is to partition a given graph G into k non-trivial components to minimize the number (or weight in the weighted case) of edges crossing the partition. This is the same as maximizing the number of edges in the partitions. Since k-way cut is NP-Hard the maximization problem is also NP-Hard. However, for fixed $k$, $k$-way cut can be solved in polynomial time. In terms of approximation here is an idea to get a simple $(1-2(k-1)/n)$-approximation which is good if $k$ is small compared to $n$. To see this, simply take the partition to be the $k-1$ smallest degree vertices and the rest of the vertices. In terms of the k-way cut the # of edges cut by this partition is at most $2(k-1)/n \cdot |E|$. Thus the number of edges remaining inside the large piece is at least $(1- 2(k-1)/n) |E|$.

Update: If the weights can be negative then I believe the problem is inapproximable via a reduction from k-coloring. Given a graph $G$, set each edge's weight to be $-1$. Thus we are seeking a $k$-partition to minimize the number of edges inside the parts. If $G$ is k-colorable then we can achieve 0, otherwise it will be at least 1. In terms of the negative weights the max value will be 0 if $G$ is k-colorable, otherwise no more than -1.