I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the question:

In MAX-3-COLOR you are given a graph $G=(V,E)$ and your goal is to find a coloring of the vertices with only 3 colors $c: V \rightarrow [3]$ that maximizes the quality function $q(c)$ - The number of edges whose endpoint vertices are colored with different colors:

$\sum_{(i,j)\in E} (1_{c(i) \neq c(j)})$

Give a probabilistic $3/2$-approximation algorithm. (i.e $q(c)\geq 2/3 \cdot OPT$ with probability at least $1-\frac{1}{e^{k}}$ for any $k \in \mathbb{N}$

OK so up until now the textbook only talks about one probabilistic algorithm which fits the requirements - MAX-3-SAT. The textbook gives a probabilistic $8/7$ - approximation algorithm for it (for every literal, toss a fair coin and decide whether to set it to $True$ or $False$).

I also found several other sources which prove that the 3-COLOR is NP-Complete by reducing it to the 3-SAT problem. Thus I am pretty confident that MAX-3-SAT is the way to go.

According to this thread: 3 Colorability reduction to SAT I thought about doing the same thing:

For every $x \in V$ create three literals: $x_1, x_2, x_3 \in \{{True, False}\}$ where each literal denotes if said vertex $x$ is colored with color $i$.

Then for every edge $e =(x,y)\in E$ create the following 3-CNF formula $\varphi$:

$ \varphi_e = (\urcorner x_1 \vee \urcorner y_1 \vee \urcorner y_1) \wedge (\urcorner x_2 \vee \urcorner y_2 \vee \urcorner y_2) \wedge (\urcorner x_3 \vee \urcorner y_3 \vee \urcorner y_3) \wedge (x_1 \vee x_2 \vee x_3)$

And the final formula $\phi$ is:

$\phi = \bigwedge_{e \in E} \varphi_e$

Every 3-CNF formula for an edge makes sure that the two endpoints are not of the same color and that one of them is either color 1, 2 or 3.

The thing is I don't see how this would help me. This gives me a MAX-3-SAT problem since I have a 3-CNF formula for every edge and one big 3-CNF formula for the whole graph. So technically I could use the same algorithm that was given in the textbook before

But wouldn't using the same probabilistic probabilistic $8/7$ - approximation algorithm for the MAX-3-SAT give the exact same approximation? whereas I wish to achieve a $3/2$- approximation

Thanks to anyone who helps!


2 Answers 2


If you simply uniformly at random (i.i.d) color each of the vertices of $V$ by each of the three possible colors, then for every edge $e\in E$, it's endpoint will be colored by different colors w.p. $\frac{2}{3}$, hence the expected quality of the random coloring is exactly $\frac{2|E|}{3}$. We know that the optimal quality is at most $q^*\leq |E|$, hence this is a $\frac{3}{2}$ approximation.

  • $\begingroup$ This is a $3/2$-approximation in expectation. To get the high probability result required by the original question, you need to run this algorithm several times and return the best of the resulting colorings. $\endgroup$
    – JeffE
    Commented May 28, 2017 at 20:36

Consider the greedy algorithm that loops through the vertices in arbitrary order and assigns each vertex $v$ the least popular color among its previously-colored neighbors. Each vertex $v$ gets a different color than at least $2/3$ of its neighbors, so the quality of the greedy coloring is at least $2|E|/3$. The optimal quality is trivially at most $|E|$, so the greedy coloring is always a $3/2$-approximation. (In particular, the greedy coloring is a $3/2$-approximation with probability at least $1-e^{-k}$ for any integer $k\in \mathbb{N}$.)

(You might object that this is not a probabilistic algorithm. Okay, whatever. In a preprocessing phase, generate a random permutation of the colors, and use this permutation to break ties in the greedy algorithm. Alternatively, flip 42 independent fair coins, and if they all come up heads, do ten jumping jacks and a lap around the football field before running the greedy algorithm.)

  • $\begingroup$ This is just the derandomization of the algorithm in the other answer, using the method of conditional expectations. $\endgroup$ Commented May 28, 2017 at 21:32
  • $\begingroup$ @YuvalFilmus In retrospect, sure. But that's not the easiest way to think about it. $\endgroup$
    – JeffE
    Commented May 28, 2017 at 21:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.