[Solved]: Minimum edge deletion partitioning

Problem Detail: 

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.

Asked By : EmreA

Answered By : Dennis Kraft

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45372

3.2K people like this

 Download Related Notes/Documents