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

ignougroup
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 $ein 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