Graph coloring/partitioning problem

Question

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

Problem $P$: 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. Let's call this sum to be the measure for $(G,w)$.

EDIT 1: A major change in the problem definition: $G$ is planar. Previously, I forgot to specify that. And, edge weights are now integers.

EDIT 2: Below text is part of the original post but it's not very useful as Mikhail Rudoy points out in his answer.

Here is what I've thought so far:

Let $k$ be the optimal number of colors, which we do not know beforehand. Suppose an oracle gives us $k$. Then, the problem becomes similar to the minimum edge deletion k-partition (MEDKP) problem, except for the fact that in MEDKP only positive weights are allowed. So, if we modify the weight function by adding a big enough constant $C$ (such that all weights become positive), i.e.

$w'(e) = w(e) + C,\;\;\;e \in E$

then using $w'$, we exactly have an instance of MEDKP.

To solve $P$, we solve MEDKP for each feasible value of $k$, i.e. $k=1 \dots |V|$. Let $M_k$ denote the set of monochromatic edges in the solution of MEDKP for $k$. Then, the solution of $P$ would be $ M_{k^*}$ where $k^* = \underset{k}{\arg\min} \sum_{e \in M_k} w(e)$.

Now, I conclude that the problem $P$ is at least as hard as MEDKP. And since MEDKP is not in APX [1], $P$ cannot be in APX either.

Is my reasoning correct? Also, independent of my reasoning above, any pointers, hints or comments on the complexity of $P$ is welcome.

Answer 1

Your problem is NP-complete. Take an instance $G'=(V',E')$ of the (NP-complete) max-cut problem. Let $m=|E'|$.

• Create two new vertices $x_1$ and $x_2$, create the edge between $x_1$ and $x_2$, and all edges between $V'$ and $\{x_1,x_2\}$.
• The edge $[x_1,x_2]$ receives positive weight $1000m$
• All edges $[x_i,v]$ with $i=1,2$ and $v\in V'$ receive negative weight $-2m$
• All edges in $E'$ receive positive weight $1$

It can be easily seen that your optimal coloring for this graph

• assigns two distinct colors to $x_1$ and $x_2$ (say color 1 to $x_1$ and color 2 to $x_2$)
• and colors every vertex $v\in V'$ with one of these colors 1 or 2

Hence, the two-coloring on $V'$ induces a max-cut in $G'$.

Answer 2

As the previous answer states, your problem is NP-hard by reduction from Max-Cut. It actually also turns out to be Poly-APX-hard by reduction from Max Independent Set (which is Poly-APX-complete). The reduction is almost a strict reduction, where the optimal solution for the instance of $P$ has as its cost the negative of the cost of the optimal solution for the Max Independent Set instance. The same reduction can also be used to prove NP-hardness.

Suppose we are given a graph $G = (V, E)$ with the task of determining the size of the maximum Independent Set, call it $I$. We reduce this to an instance of problem $P$ as follows:

Let $G' = (V', E')$ where $V' = V \cup \{x\}$ and $E' = E \cup \{(x, v) | v \in V\}$ and let $w : E' \rightarrow \mathbb{Z}^+$ be a weighting of the edges such that whenever $e \in E$ we have $w(e) = |V|$ and whenever $e = (x, v)$ for some $v \in V$ we have $w(e) = -1$.

We claim that the measure for $(G', w)$ is $-|I|$.

Consider the coloring of $G'$ which assigns one color to the set $I \cup \{x\}$ and assigns every other vertex a unique color. Under that coloring, the only monochromatic edges are those with both endpoints in $I \cup \{x\}$. Since the subgraph in $G'$ induced by the vertex set $V$ is exactly the graph $G$, and since $I$ is an independent set in $G$, we know that there are no edges with both endpoints in $I$. Thus the only monochromatic edges in $G'$ are those of the form $(x, v)$ where $v \in I$. There are $|I|$ such edges, each with weight $-1$, so the total weight of all monochromatic edges under this coloring is $-|I|$. The measure for $(G', w)$ is then bounded above by the value $-|I|$.

Next suppose for the sake of contradiction that the measure for $(G, w)$ is less than $-|I|$.

Every negatively weighted edge in $G'$ has weight $-1$. Therefore, in order for the total weight of the monochromatic edges to be less than $-|I|$, there must be more than $|I|$ monochromatic edges of weight $-1$ in $G'$. Every edge of weight $-1$ has $x$ as one end-point. Then since these edges are monochromatic, the other endpoints all have the same color. Thus, we have accumulated a set of vertices $I' \in V$ with $|I'| > |I|$ that are all the same color. Since $I$ is the maximum independent set in $G$, we know that $I'$ is not an independent set, and so there exists an edge $(u, v) \in E$ with endpoints in $I'$. This edge is then monochromatic, and contributes a total of $w((u, v)) = |V|$ to the sum of the weights of the monochromatic edges. The total weight of all of the negatively weighted edges in all of $G'$ is $-|V|$, so already the total monochromatic weight under this coloring must be non-negative. This contradicts the fact that the total weight of the monochromatic edges is supposed to be less than $-|I|$.

By contradiction, the measure of $(G', w)$ must be exactly $-|I|$.

The above should also be enough to see how a solution to the problem $P$ instance can be used to solve the Max independent Set instance (by taking the set of vertices of the same color as $x$ to be the independent set) though we will not go through the details here.

As a result, the above is an approximation-preserving reduction that is sufficient to show that problem $P$ is Poly-APX-hard.

---

Now a few notes:

Your reasoning was a bit off in several places.

First of all, you described a reduction from $P$ to MEDKP (you solved an instance of $P$ by solving several instances of MEDKP) and concluded that $P$ is at least as hard as MEDKP. In fact, that is backwards. What you can actually conclude is that MEDKP is at least as hard as $P$. To make it clearer, consider the version of problem $P$ that you get if you restrict weights to be non-negative. This problem is trivial, since the measure of every instance $(G, w)$ will always by zero (by taking a coloring where each vertex is uniquely colored). However, your argument applies to this problem without modification (you could solve this problem using several instances of MEDKP). If you were to conclude that that problem is at least as hard as MEDKP, then you would have proved that MEDKP is trivial, which it is clearly not.

The second issue I saw was in the construction of weights $w'$. The issue is that modifying the weights leads to the problem changing. When you increase the weights as you did, the total weight of the monochromatic edges in a coloring is itself increased by a value of $C$ for each monochromatic edge. Therefore the total weight of the monochromatic edges changes by different amounts for different colorings, depending on the number of monochromatic edges in the coloring. The optimal coloring could then change! For example, if you take an instance of $P$ produced by the reduction I provided above, finding an optimal coloring is computationally difficult. On the other hand, if you move all the weights up even just by one, the optimal coloring is trivial to find (simply take a coloring with each vertex uniquely colored). Clearly, the problem has changed since the tractability of solving it has changed so much.

Next, I was wondering about whether you had a reason to generalize to real numbers and not just generalize to all integers. Dealing with integers makes things easier in several ways. For one thing, it is intuitively clear how to encode an integer, and not so much so for a real number; depending on your encoding of real numbers, it could be possibly to embed all sorts of difficult problems into $P$ in ways that don't actually shed any light on the nature of $P$ (i.e. you would be forced to solve the sum-of-square-roots problem (see online; cou) in a situation where you had to compare two solutions whose values were each sums of square roots). In addition, it is much more obvious how to discuss terms like "polynomial in the size of the input" when the size of the input is easy to determine from the size of the numbers in the input. In particular, the integer version of $P$ is clearly in NP (and therefore NP-complete) while the real number version is of some unknown difficulty.

I also want to note that I couldn't think of a polynomial factor approximation algorithm for $P$ (either the real number or integer version), and so just like with the NP-hardness result, $P$ is Poly-APX-hard but not necessarily Poly-APX-complete. I would be very interested in seeing further results in either direction.

Finally, I wanted to say that I really liked the problem and found it very interesting to think about; thanks!