4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It normally has a reason that such a $k$ is fixed beforehand. Otherwise it is not possible to formulate it as decision problem (aka "yes/no") as all the other NP-complete problems. Plus, once you can decide, given a $k$, whether the graph has a coloring with weights less than $k$, you can use binary search to find the optimal $k$. $\endgroup$ – john_leo Aug 18 '15 at 15:14
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks! How about if G was a planar graph in my original post? $\endgroup$ – EmreA Aug 31 '15 at 12:31
  • $\begingroup$ Interesting question. Honestly, I have no idea at the moment. $\endgroup$ – Dennis Kraft Sep 1 '15 at 15:00
1
$\begingroup$

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).

$\endgroup$

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.