m Coloring Problem

The problem, simply

You get a graph: n dots, some of them joined by lines. You also get a number m, the number of colors you may use.

Can you give each dot a color, using at most m colors, so that no line joins two dots of the same color? Answer true or false.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every way to color all the dots, and check each full coloring at the end.

1. Give dot 0 each of the m colors, and for each, give dot 1 each color, and so on, until every dot has a color.
2. When all dots are colored, check every line. If no line joins two equal colors, answer true.
3. If no full coloring works, answer false.

import java.util.*;

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

    private boolean tryAll(int v, int[] color, int n, int[][] edges, int m) {
        if (v == n) {                                   // everyone has a color, check now
            for (int[] e : edges) {
                if (color[e[0]] == color[e[1]]) return false;
            }
            return true;
        }
        for (int c = 1; c <= m; c++) {
            color[v] = c;
            if (tryAll(v + 1, color, n, edges, m)) return true;
        }
        return false;
    }
}

How long it takes: there are m^n full colorings and each check reads all e lines, so O(m^n * (n + e)). Extra room: the color array and the call stack, O(n).

The waste is clear: if dots 0 and 1 are joined and both red, Way 1 still colors all the other dots before noticing.

Way 2: the clever way

Check as you go. Before painting a dot, look at its neighbors. If one of them already has this color, skip it right away. A bad choice is caught at the first dot where it matters, and the whole branch under it is never built.

1. Color the dots in order 0, 1, 2, and so on.
2. For the current dot, try colors 1 to m. A color is safe if no neighbor already has it.
3. If safe, paint it and move to the next dot. If that leads to a full coloring, answer true.
4. If not, wipe the color off and try the next one. This is the backtracking step.
5. If no color works, return false so the dot before can change.

import java.util.*;

class Solution {
    public boolean graphColoring(int n, int[][] edges, int m) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        return paint(0, new int[n], adj, m);
    }

    private boolean paint(int v, int[] color, List<List<Integer>> adj, int m) {
        if (v == color.length) return true;              // every dot is painted
        for (int c = 1; c <= m; c++) {
            if (isSafe(v, c, color, adj)) {
                color[v] = c;
                if (paint(v + 1, color, adj, m)) return true;
                color[v] = 0;                            // wipe off and try the next color
            }
        }
        return false;                                    // no color fits, go back
    }

    private boolean isSafe(int v, int c, int[] color, List<List<Integer>> adj) {
        for (int u : adj.get(v)) {
            if (color[u] == c) return false;             // a neighbor already has it
        }
        return true;
    }
}

How long it takes: the worst case is still m^n paintings, and each safety check reads the dot's neighbors, at most n, so O(m^n * n). In practice the early checks cut away most of the tree. Extra room: the colors and the call stack, O(n), besides the neighbor lists that store the graph.

Watch out for

• Forgetting that lines go both ways. Add each edge to both dots' neighbor lists.
• Not resetting color[v] = 0 after a failed try. Old colors left behind make later safety checks wrong.
• Dots with no lines still need a color. The base case is "all n dots done", not "all lines checked".
• A graph in several pieces is fine. The loop over dots covers every piece.

What interviewers ask next

• Only 2 colors? Then you do not need backtracking. Run breadth first search and give each neighbor the other color. If a line ever joins two equal colors, the answer is false. That is the bipartite check, O(n + e).
• What is the smallest m that works (the chromatic number)? Try m = 1, 2, 3, ... until it succeeds. It is NP-hard, so no fast method is known in general.
• How can you prune more? Fix dot 0 to color 1, because colors can be renamed. And color the dot with the fewest safe colors left first (this is called DSATUR), so dead ends appear early.
• Where is this used? Exam timetables (subjects that share a student cannot share a slot), radio frequencies, and register allocation in compilers. Sudoku is coloring with 9 colors.

Remember this

Grown-up words: dots are vertices, lines are edges, the colors are labels in a proper vertex coloring, the smallest number of colors is the chromatic number, and checking before going deeper is pruning in backtracking.