Minimum edge deletion partitioning

Question

I'm interested in the time complexity of the following problem:

Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the vertices in such a way that the sum of the weights of the monochromatic edges (i.e. those between same color vertices) is minimized.

The closest NP-hard problem I could find is the "minimum edge deletion k-partition" (https://www.nada.kth.se/~viggo/wwwcompendium/node43.html), however, in that problem $k$ is known and fixed beforehand, whereas in my problem, the optimal $k$ (i.e. the number of different colors) is not known.

Any hints, pointers, comments are welcome.

Answer 1

I believe this problem is NP-hard and it can be shown by a reduction from the vertex coloring problem with $k$ colors.

Assume we are given a graph $G' = (E',V')$ and we want to decide whether there exists a coloring of the vertices in $V'$ using only $k$ colors. To do so, we construct a new graph $G$ that consists of $G'$ as well as the complete graph $K_k$. Furthermore, we add edges of weight $-1$ from every vertex in $G'$ to every vertex in $K_k$. The edges inside of $G'$ as well as $K_k$ on the other hand have a very large weight.

Now, I claim that $G'$ admits a $k$-coloring, if and only if we can color $G$ and achieve a profit of $|V'|$. To see this, we first observe, that due to the large weight on the edges inside of $G'$ and $K_k$, both sub-components must be colored in such a way that no adjacent vertices inside of them share the same color. For $K_k$, this trivially implies a $k$-coloring. Next, note that all vertices with matching colors between $G'$ and $K_k$ add a profit of one to the total profit. However, there can be at most one such edge between $G'$ and $K_k$ for every vertex in $G'$. This is exactly the case if $G'$ has a $k$-coloring (using the same colors that were used in $K_k$). Thus $G'$ admits a $k$-coloring if and only if we can find a coloring of $G$ with a profit of $|V'|$. This in turn implies NP-hardness of your problem.

Answer 2

Interesting problem. Here are some results for some special cases.

If all weights are negative then colour every vertex in the same colour. This will be optimal.

if G is planar and all weights are positive then you can colour its vertices with 4 colours such that no two connected vertices are the same colour (no monochromatic edges). This is due to the 4-color theorem. With no monochromatic edges you will get a sum of 0 and this will be optimal. If G is non-planar and all weights are positive then the chromatic number of G gives you the minimum number of colours needed to obtain zero monochromatic edges:

http://mathworld.wolfram.com/VertexColoring.html

http://mathworld.wolfram.com/ChromaticNumber.html

For the general problem I can't find any quick solution. The closest is what you have mentioned already: minimum edge deletion k-partition = minimum k-partition. Suppose you had a solution to this problem for a given k, call it f(k). Find f(1), then f(2), then f(3) and so on, each time recording the best result. You can terminate as soon as you have found a k such that f(k)=f(k-1).