Randomized Coloring

Randomized algorithm for $(\Delta+1)$-coloring and maximal independent set in $O(\log n)$ time on general graphs.

Recall Some Math

$1-x\leq e^{-x}\forall x\in\mathbb R$

$1-x\ge4^{-x}\forall x\in[0,\frac{1}{2}]$

$\lim_{x\to\infty}(1-\frac{1}{x})^x=\frac{1}{e}$

Simple Idea

Each node picks a random color. If there is no conflict, the node will keep the color and terminate. Otherwise repeat picking until no conflict. _~Very hard to show the expected running time analysis._~

Lemma: In the first round, if each node picks a color independently and uniformly at random, $$ \Pr{v\text{ picks a different color to its neighbor}}\ge\frac{1}{e}. $$ Proof: Fix a neighbor $u$, $\Pr\{x_v=x_u\}=\frac{1}{\Delta+1}$, thus $\Pr\{x_v\neq x_u\}=\frac{\Delta}{\Delta+1}$. $$ \Pr{v\text{ picks a different color to its neighbor}}=(\frac{\Delta}{\Delta+1})^\Delta\geq\frac{1}{e}. $$ But in the following rounds, the inequality does not hold.

Change the Algorithm

Each node picks a random bit $b$. For node $v$:

If $b=0$, $v$ does nothing.
If $b=1$, $v$ picks a color from free colors uniformly at random.

Send and receive the color to and from its neighbors.

If no confliction, $v$ keeps the color and terminate.

Analysis

Theorem: In each round, for a uncolored node $v$: $\Pr\{v\text{ is colored}\}\ge\frac{1}{4}$.

$v$ is active if $b=1$.

Let $f_v$ be the number of free colors of $v$, $k_v$ be the number of uncolored neighbors of $v$.

Obviously, $k_v\geq f_v$. (Otherwise the coloring can't be done)

Fix a neighbor $u$, we have: $$ \Pr{v\text{ collides with }u|v\text{ is active}}=\Pr{u\text{ is active}}\cdot\Pr{v\text{ picks the same color as }u}\leq\frac{1}{2}\cdot\frac{1}{f_v}. $$ By union bound, there are $k_v$ uncolored neighbors. $$ \Pr{v\text{ picks the same color as some neighbors}|v\text{ is active}}=\frac{k_v}{2f_v}\leq\frac{1}{2}. $$ Thus, $$ \Pr{v\text{ fix a color}}=\Pr{v\text{ is active}}\cdot\Pr{v\text{ has no confliction}}\geq\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}. $$ Q.E.D.

After $T$ rounds, the probability the node $v$ doesn't terminate: $$ \Pr{v\text{ is uncolored after }T\text{ rounds}}\leq(\frac{3}{4})^T. $$ By union bound, the probability the algorithm doesn't terminate: $$ \Pr{\exists v:v\text{ is uncolored after }T\text{ rounds}}\leq n\cdot(\frac{3}{4})^T. $$ If we insert $T=O(\log n)$, the probability the algorithm doesn't terminate is ${1/n^c}$.

Randomized Maximal Independent Set

Simple Idea

Assign a random ID on each node, then run greedy algorithm.

The algorithm will terminate with high probability in $O(\log n)$ rounds, ~~but difficult to analyze~~.

Luby's Algorithm

At each round,

the node $v$ picks a random number $R_v\in[0,1]$.
$v$ joins MIS if $R_v<$ any number that the neighbor of $v$ picks.
Remove $v$ and its neighbors from the graph.

\[ \Pr\{v\text{ joins MIS}\}=\frac{1}{\deg(v)+1}. \]

Each round, we remove constant portion of nodes? NO!!!

Show that in each round, we remove constant portion of edges!

For edge $(u,v)$, let the incident $\epsilon_{u,v}$ be: $\forall w\in N(u)\cup N(v)\backslash\{u\}:x_u<x_w$

$\epsilon_{u,v}$ is true: all edges of $v$ is removed because of $u$

$\epsilon_{v,u}$ is true: all edges of $u$ is removed because of $v$

Define the variable $$ x_{u,v}=\begin{cases} \deg(v)\text{ if }\epsilon_{u,v}\ 0\text{ otherwise} \end{cases} $$ and the number of edges $x$ $$ x=\sum_{(u,v)\in E}(x_{u,v}+x_{v,u}), $$ we have $x\leq 2\cdot$ the number of deleted edges.

Each round, we remove half of the edges in expectation.

From MIS to Coloring

Extended Graph

We extend the graph by adding $\Delta$ copies. ($\Delta+1$ copies in total) Each copy corresponds a color.

Each corresponding node in the copies have connections to each other (clique).

Reduction

Run MIS on the extended graph.

In the MIS results, each node appears at least once in each column.

Then the node pick the column number as its color.