3-Colouring Problem

computation

Definition

3-Colouring Problem

The 3-colouring problem is a decision problem.

Instance: an undirected graph $G=(V,E)$

Question: Does there exist a colouring of the vertices of $G$ with three colours such that adjacent vertices always have different colours?

NP-Membership

The 3-colouring problem is in NP. There are several equivalent ways to show this.

Let

$$R=\{((V,E),f)\mid f(v_i)\ne f(v_j)\text{ for all }{v}_i,v_j\in V\text{ with }[v_i,v_j]\in E\}.$$

Here, the certificate is a colouring function $f:V\to \{1,2,3\}$.

Why this proves NP-membership

A proposed colouring $f$ has size polynomial in $|V|$, and we can verify it in polynomial time by checking for every edge $[v_i,v_j]\in E$ that $f(v_i)\ne f(v_j)$.

Therefore, the 3-colouring problem has a polynomial-time verifier, so it belongs to NP.

A nondeterministic algorithm may guess one of three colours for each vertex and then check in polynomial time whether the resulting assignment is a valid 3-colouring.

Reductions

Reduction to SAT

Let $G=(V,E)$ be an instance of the 3-colouring problem with

$$V=\{v_1,\dots ,v_n\}.$$

For each vertex $v_i$ and each colour $c\in \{r,g,b\}$, introduce a propositional variable $a_i^c$.

The intended meaning is that $a_i^c$ is true exactly when vertex $v_i$ has colour $c$.

We define a reduction $R$ that maps $G$ to the SAT instance

$$R(G)={\phi }_G={\phi }_1\wedge {\phi }_2\wedge {\phi }_3,$$

where:

$${\phi }_1=\underset{1\le i\le n}{\bigwedge }(a_i^r\vee a_i^g\vee a_i^b)$$

ensures that every vertex gets at least one colour,

$${\phi }_2=\underset{1\le i\le n}{\bigwedge }(\neg (a_i^r\wedge a_i^g)\wedge \neg (a_i^r\wedge a_i^b)\wedge \neg (a_i^g\wedge a_i^b))$$

ensures that no vertex gets two different colours at the same time, and

$${\phi }_3=\underset{[v_i,v_j]\in E}{\bigwedge }(\neg (a_i^r\wedge a_j^r)\wedge \neg (a_i^g\wedge a_j^g)\wedge \neg (a_i^b\wedge a_j^b))$$

ensures that adjacent vertices do not receive the same colour.

Therefore, $G$ is 3-colourable if and only if ${\phi }_G$ is satisfiable.

Branching

The trivial deterministic algorithm tries all three colours for every vertex. For $n=|V|$, this gives roughly

$$O(3^n\cdot n)$$

time, up to the cost of checking a colouring.

For 3-colouring, one can do better than this basic branching by using two facts:

1. the names of the three colours are symmetric;
2. a vertex adjacent to an already coloured vertex has at most two compatible colours left.

First assume the input graph is connected. If an algorithm works for connected graphs, disconnected graphs can be handled by solving each connected component separately.

Choose one vertex $v_0$, assign it an arbitrary colour, say red, and mark it as processed. This loses no generality: if a valid colouring uses another colour for $v_0$, the colour names can be renamed.

Then repeatedly choose an unprocessed vertex $w$ that is adjacent to at least one processed vertex. Such a vertex exists as long as the graph is connected and some vertex is still unprocessed. Branch only over colours for $w$ that are compatible with the colours of neighbouring processed vertices.

Since $w$ has at least one processed neighbour, at least one colour is forbidden. Therefore $w$ has either one or two possible colours available, never three.

The running time follows from the branching tree. The first vertex has only one option, because its colour may be fixed by symmetry. Every later vertex has at most two options. At each step, it takes at most $O(n)$ time to find the next vertex and check which colours are compatible with its processed neighbours.

Therefore 3-colouring can be solved exactly and deterministically in time

$$O(2^n\cdot n),$$

where $n$ is the number of vertices. In O-star notation, this is

$$O^{\ast }(2^n).$$

This breaks the trivial $O(3^n\cdot n)$ barrier.

More advanced exact algorithms improve the base further. For example, 3-colouring can be solved in time

$$O^{\ast }(1.33^n),$$

where $n$ is the number of vertices.