2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The problem is NP-Hard via a reduction from minimum k-way cut. In min k-way cut we want to partition the graph into k parts to minimize the sum of the edges across the cut. Your problem is the complement. $\endgroup$ – Chandra Chekuri Apr 20 '16 at 13:21
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your suggestion,but if the weights of Graph G could be negative or non-negative,lets say some of them are negative and others are not,I want to know could the minimum K-way cut solve the problem in this condition? $\endgroup$ – krystal Apr 22 '16 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.