Vertex Coloring VS MIS

	Coloring	MIS
Nodes	neighbors get different colors	some are selected to form a independent set
Objectives	the number of colors is as small as possible	the independent set is maximal

Usually the target number of colors is $\Delta+1$. Sometimes we want less colors.

On Coloring

Local minima algorithm which takes $\Theta(n)$ rounds and computes $\Delta+1$-coloring.

It works on general graphs as well.

Cole-Vishkin computes $6$-coloring in $\Theta(\log^*n)$ rounds.

Important: we have a consistent orientation where each node has a unique successor.

Coloring Rooted Trees

Rooted trees

Graph is a tree, each node knows which neighbor is its parent
The root knows it is the root.

2-coloring

Time complexity: $\Theta(Depth)$.

This is tight, because nodes need to know the parity of their distance to the root.

Very inefficient.

More Colors

Each node has exactly one parent (successor)

The Cole-Vishkin color-reduction directly works on rooted trees.

From 6 to 3 Colors

Coloring rooted trees:

$2$-coloring requires $\Omega(Depth)$
$6$-coloring requires $O(\log^*n)$ rounds
What about $3,4,5$ colors?

Reducing from $6$ to $5$ colors:

Can we recolor nodes with color $5$ with a smaller color? Yes.

Shift Down Colors

The root chooses the smallest color different from its own.

Every other node takes the color of its parent

As a consequence, for every node $v$, all children of $v$ have the same color.

Color-Reduction Step

Each node of color $C$ takes the smallest free color

For each node of color $C$, there is a free color in $\{0,1,2\}$

As long as the number of colors is larger than $3$, we can reduce the number of colors by one in two rounds.

Coloring Directed Pseudoforests

Pseudoforest

A graph in which each connected component has at most one cycle.

Directed Pseudoforest

A graph where the out-degree of every node is at most $1$.

Claim: The $3$-coloring algorithm for rooted trees can also be applied in a directed pseudoforest.

Nodes with out-degree $1$ treat their out-neighbors as parent
Other nodes behave like the root and imagine an out-neighbor with some different color.

From $6$ to $3$ colors, algorithm also works in the same way.

Shift down: every node with out-degree $1$ picks the color of their out-neighbor, the root nodes pick the smallest free color.
Reduce colors: all in-neighbors of a node have the same color and each node therefore only sees $2$ different colors among its neighbors.

Coloring Graphs with Maximum Degree

We first orient each edge on the graph arbitrarily.

For example, we orient edge $(u,v)$ from $u$ to $v$ iff $ID(u)<ID(v)$.

Induced Subgraphs

Assume that a node $v$ has $d_v$ outgoing edges. Node $v$ labels these edges from $1$ to $d_v$.

Then in $\Delta$ rounds, each node label a incident edge.

The subgraph $G_i$ induced by edges labeled with $i$ is a directed pseudoforest.
There are $\Delta$ induced subgraphs in total.

For each induced subgraph, compute, in parallel, a $3$-coloring of $G_i$ in $O(\log^*n)$ rounds.

Each node $v$ then gets a vector $c_v\in\{0,1,2\}^\Delta$ of colors, where $c_{v,i}$ is the color of $v$ in graph $G_i$.

Thus, there is a distribute algorithm that computes a $3^\Delta$-coloring in $O(\log^*n)$ rounds.

Bounded-Degree

If $\Delta=O(1)$, then $3^\Delta=O(1)$, we get $O(1)$-coloring in $O(\log^*n)$ rounds.

But we want $(\Delta+1)$-coloring.

Trivially, from $3^\Delta$ to $(\Delta+1)$ colors it takes $O(3^\Delta)$ rounds. Can we improve this to polynomial of $\Delta$?

Yes, we can reduce from $3^\Delta$ to $\Delta+1$ in $O(\Delta^2)$ rounds.

By induction:

Base case: $G_1$ is colored with $3$ colors.

Inductive step: Assume that $G_{\leq i}$ is colored with $\Delta+1$ colors

Show: how to color $G_{\leq i+1}$ with $\Delta+1$ colors

$G_{i+1}$ is colored with $3$ colors, and hence $G_{\leq i+1}$ is colored with $3(\Delta+1)$ colors.

Use the local minima algorithm and reduce to $(\Delta+1)$ colors: $O(\Delta)$ rounds.

The color reduction is done for $\Delta$ times, and each takes $O(\Delta)$ rounds, hence in total this operation is done in $O(\Delta^2)$ rounds.

For a graph with maximum degree $\Delta$, there is a distributed algorithm that computes a $(\Delta+1)$-coloring in $O(\Delta^2+\log^* n)$ rounds.

SOTA: $O(\sqrt{\Delta\log\Delta}+\log^*n)$.

Open problem: what's is the tight bound for this problem?

Coloring Unrooted Trees

Electing a root and orienting costs $\Theta(Depth)$ rounds.

Rooted tree: out-degree of each node is at most $1$.

Graphs of max degree $\Delta$: out-degree of each node is at most $\Delta$.

Orientation with Max Degree 2

If we can compute the orientation with max degree $2$... (which would give a $9$-coloring)

Observation 1: Computing an orientation with out-degree $\leq 2$ is trivial for degree $\leq 2$. (just orient arbitrarily).

Observation 2: In an $n$-node tree, at least $n/3$ nodes have degree $\leq 2$.

number of edges: $n-1$.

By hand-shaking theorem, sum of degrees is $2n-2<2n$.

Assume that $k$ nodes have degree $\geq3$, we have $$ \sum_{v\in V}\deg(v)\geq 3k<2n\Rightarrow k<2n/3. $$

Each time, we find all nodes having $\leq2$ degree, put them in a layer, and discard them.

Afterwards, we have $O(\log n)$ layers.

Edges inside the layer, we orient them arbitrarily
Edges between the layers, we orient from the smallest to largest

9-coloring Unrooted Trees

Compute an orientation with out-degree $\leq2$ in $O(\log n)$ rounds.

This creates two directed forests.

Color each forest with $3$ colors in $O(\log^* n)$ rounds.

Each node $v$ that has two colors for each forest.
The total number of colors used is $3^2=9$.
For every edge $(u,v)$, we have $c_{u,1}\neq c_{v,1}$ or $c_{u,2}\neq c_{v,2}$.

It's possible to obtain $3$ colors.

Rake and Compress

A generalization of the algorithm for unrooted trees $T$:

for $i=1$ to $k$:

Rake: $R_i=$ nodes of degree 1; remove nodes of $R_i$ from $T$
Compress: $C_i=$ nodes of degree $2$; remove nodes of $C_i$ from $T$

This gives a nice tree decomposition.

Guarantees:

After $k=O(\log n)$ steps, $T$ becomes empty.
All nodes in $R_i$ have at most $1$ neighbor in the same or higher layers.
All nodes in $C_i$ have at most $2$ neighbors in same or higher layers.

Applications

3-coloring

maximal matching

edge orientations