10
$\begingroup$

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

Given an undirected planar 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. There is no limit on the number of colors you can use. Note that it is not necessarily optimal to give each vertex a distinct color as negative edge weights are possible.

A version of this problem where $G$ is not restricted to be a planar graph is NP-hard (see Minimum edge deletion partitioning) by a reduction from the vertex coloring problem. However, we cannot use the same reduction for the problem here because $G$ is planar.

Any hints, pointers, comments are welcome.

Improve this question
$\endgroup$
5
  • $\begingroup$ The number of colors is given, right? $\endgroup$
    – André Souza Lemos
    Commented Aug 31, 2015 at 15:46
  • $\begingroup$ No, it's not given. $\endgroup$
    – EmreA
    Commented Aug 31, 2015 at 18:17
  • 1
    $\begingroup$ I've edited the question to reflect your comment that the number of colors is unlimited. In the future, when someone asks a clarification question, please edit the question -- don't just leave clarifications in the comments, as people shouldn't have to read the comments to understand your question. The source of the confusion might have been: if edge weights are non-negative, and if there's no limit on the number of colors, the problem is trivial: just assign each vertex its own color. However in this problem edge weights can be negative, so the trivial solution isn't necessarily optimal. $\endgroup$
    – D.W. ♦
    Commented Aug 31, 2015 at 21:48
  • $\begingroup$ The interesting property of planar graphs in this context seems to be that they are 4-colorable. As D.W. pointed out however, the optimum for your problem doesn't depend on using a minimum number of colors, so intuitively the planar restriction shouldn't affect the complexity. I have a hunch the reduction given by Dennis Kraft would still hold, because you're not considering the planar input graph coloring in isolation, but I might just as well be wrong. $\endgroup$
    – Fasermaler
    Commented Sep 9, 2015 at 14:39
  • $\begingroup$ If you restrict the number of colors to 2, then the problem is equivalent to max-cut (with possibly negative edge weights), which is NP-hard for general graphs but solvable in polynomial time for planar graphs. So maybe planarity could help here as well. $\endgroup$
    – Lê Thành Dũng 'Tito' Nguyễn
    Commented Nov 4, 2022 at 19:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.