M-Colouring Problem

The problem, simply

You get a graph with V countries (dots) and some borders (lines), and a number m. Can you give every country one of m colours so that two countries sharing a border never have the same colour?

Answer true or false. Many versions also ask you to print one colouring that works.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every way to colour the map, then check each one. With m colours and V countries there are m^V ways.

1. Give country 0 each colour in turn, and for each, give country 1 each colour, and so on, without looking at borders.
2. When all countries have a colour, check every border. If no border joins two equal colours, answer true.
3. If no way passes, answer false.

import java.util.*;

class Solution {
    public boolean graphColoring(int V, int[][] edges, int m) {
        return tryAll(new int[V], 0, V, edges, m);
    }

    private boolean tryAll(int[] colour, int u, int V, int[][] edges, int m) {
        if (u == V) {                                  // everyone has a colour: check now
            for (int[] e : edges) if (colour[e[0]] == colour[e[1]]) return false;
            return true;
        }
        for (int c = 1; c <= m; c++) {
            colour[u] = c;                             // no checking yet
            if (tryAll(colour, u + 1, V, edges, m)) return true;
        }
        return false;
    }
}

How long it takes: m^V full colourings, each checked against all borders, O(m^V * (V + E)). Extra room: the colour array and the recursion, O(V).

Way 2: the clever way

Check as you go. Before giving a country a colour, look at its neighbours. If one of them already has that colour, do not even try it. A bad choice is caught at the country where it goes wrong, not after the whole map is painted, so whole branches of tries are skipped. This is backtracking.

1. solve(u): if u == V, everyone is coloured, return true.
2. For each colour c from 1 to m: if no neighbour of u has c, set colour[u] = c and call solve(u + 1). If it returns true, return true.
3. Otherwise erase colour[u] and try the next colour.
4. If no colour works, return false so the country before can change.

import java.util.*;

class Solution {
    public boolean graphColoring(int V, int[][] edges, int m) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        return solve(adj, new int[V], 0, m);          // 0 means no colour yet
    }

    private boolean solve(List<List<Integer>> adj, int[] colour, int u, int m) {
        if (u == colour.length) return true;          // every country is coloured
        for (int c = 1; c <= m; c++) {
            if (safe(adj, colour, u, c)) {
                colour[u] = c;
                if (solve(adj, colour, u + 1, m)) return true;
                colour[u] = 0;                        // erase and try the next crayon
            }
        }
        return false;                                 // stuck: let the caller change
    }

    private boolean safe(List<List<Integer>> adj, int[] colour, int u, int c) {
        for (int v : adj.get(u)) if (colour[v] == c) return false;
        return true;
    }
}

How long it takes: in the worst case the search still tries about m^V paths, and each step checks one country's neighbours, so O(m^V * V). In practice the early checks cut away most branches. Extra room: the colour array and the recursion, O(V).

Watch out for

• A graph in pieces. Colouring country by country in number order handles every piece, because every country gets its turn.
• Counting colours from 0 while also using 0 for "no colour". Use 1 to m for colours, or -1 for empty.
• Borders listed once. Add each border to both countries' lists.
• When m >= V, the answer is always true: every country can have its own colour. When m == 1, the answer is true only if there are no borders.

What interviewers ask next

• How do you make it faster in practice? Colour the country with the fewest colours left first (most constrained first), and colour countries with many neighbours early.
• When m = 2, is there a fast way? Yes. Breadth first search can check two-colouring (bipartite) in O(V + E). For m >= 3 no fast method is known; it is NP complete.
• How do you find the smallest m that works? Try m = 1, 2, 3, ... with this search and stop at the first true. That number is the chromatic number.
• Is greedy colouring enough? Greedy is fast and always valid, but it can use more colours than needed, so it cannot prove that m colours are impossible.
• Sudoku and exam timetables are the same idea: each cell or exam is a country, each conflict is a border, and the digits or time slots are the colours.

Remember this

Grown-up words: countries are vertices, borders are edges, crayons are colours, checking a colour before using it is the safety check, erasing and retrying is backtracking, and the smallest number of crayons that works is the chromatic number.