[Solved]: 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR

Problem Detail: 

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!

Asked By : user475680

Answered By : R B

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.

Best Answer from StackOverflow

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