today i came across this chinese blog about randomized algorithms and thought it lacked a little more details. moreover, i haven’t found any blogs about this algorithm and i thought the idea behind it was really interesting and could provide some inspiration for problem setters.

the problem is simple: finding a 3-coloring of a graph. we all know it’s NP hard but this is when randomization comes in handy.

let’s fix the color of one vertex to avoid finding symmetrical colorings, and for each vertex let’s set a forbidden color in the set $\{0, 1, 2\}$ at random.

can we color our graph using the colors we’re allowed to use? we can check this modeling the constraints as an instance of 2SAT.

2SAT?

for each vertex $u$, let $S_u = \{x, y\}$ be its set of allowed colors $(x < y)$. we define $c_u$ as the boolean variable that equals $0$ if $color(u) = x$ and $1$ if $color(u) = y$.

now, we add the color restrictions on edges $e = uv$ depending on the color sets. for example, if $S_u = \{0, 1\}$ and $S_v = \{1, 2\}$, we will add the following constraint.

$\neg c_u \lor c_v$

why does this work? if $color(u) = 0$ the clause is obviously true and this makes sense since $0$ isnt allowed in $v$, so any color choice from the other vertex would be ok.
on the other hand, if $color(u) = 1$, $color(v)$ has to equal $2$, otherwise we’d have two edges with the same color.

bounds on probabilities

this algorithm has a success probability lower bound of $(\frac 2 3)^n$. this can be proven by taking an arbitrary valid 3-coloring and seeing that for each node we’re not discarding the right color with probability $\frac 2 3$.

this means, if we want to find a solution with a probability of $1-\varepsilon$, we can repeat our algorithm

$-(\frac 3 2)^n \log(\varepsilon)$

times.

is this good?

the expected number of trials to get a correct answer is $(\frac 3 2)^n$, so the average runtime is $O((n+m)(\frac 3 2)^n)$ which is, sadly, exponential.

for $n \approx 30$, we’d need around $2 \cdot 10^5$ iterations, and for higher numbers the algorithm would run forever.

so, is this good? no!!! but the idea behind it is pretty neat, which is why i posted this :>

maybe if the graph is random and sparse enough or its known to have multiple 3-colorings, the expected number of trials could be way smaller and this algorithm could be actually good. maybe if we combine it with pruning? i don’t know, though if i end up finding a way to optimize it im gonna post it here. (spoiler: i wont)