3-Colouring Problem

computation

Definition

3-Colouring Problem

The 3-colouring problem is a decision problem.

Instance: an undirected graph

Question: Does there exist a colouring of the vertices of 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

Here, the certificate is a colouring function .

Why this proves NP-membership

A proposed colouring has size polynomial in , and we can verify it in polynomial time by checking for every edge that .

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 be an instance of the 3-colouring problem with

For each vertex and each colour , introduce a propositional variable .

The intended meaning is that is true exactly when vertex has colour .

We define a reduction that maps to the SAT instance

where:

ensures that every vertex gets at least one colour,

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

ensures that adjacent vertices do not receive the same colour.

Therefore, is 3-colourable if and only if is satisfiable.

Branching

The trivial deterministic algorithm tries all three colours for every vertex. For , this gives roughly

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 , assign it an arbitrary colour, say red, and mark it as processed. This loses no generality: if a valid colouring uses another colour for , the colour names can be renamed.

Then repeatedly choose an unprocessed vertex 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 that are compatible with the colours of neighbouring processed vertices.

Since has at least one processed neighbour, at least one colour is forbidden. Therefore 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 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

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

This breaks the trivial barrier.

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

where is the number of vertices.