Problem

Network decomposition

A $(C, D)$-network decomposition of a graph $G = (V, E)$ partitions the nodes into clusters of diameter at most $D$ and colors the clusters with $C$ colors so that adjacent clusters get different colors. The diameter is weak if it is measured in $G$ and strong if it is measured inside the cluster.

Every graph has a decomposition with $C = \mathcal{O}(\log n)$ and $D = \mathcal{O}(\log n)$. Given one, MIS, $(\Delta+1)$-coloring and many other problems can be solved in $\mathcal{O}(C \cdot D)$ rounds by going through the colors one by one (see the reductions).

Runtimes are given in rounds, in terms of the number of nodes $n$.

A network decomposition A graph with twelve nodes in four clusters of three nodes each. Diagonally opposite clusters share a color, so adjacent clusters always have different colors.
Four clusters of diameter 1, colored so that adjacent clusters differ: a $(2, 1)$-network decomposition.