☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

M Coloring Problem

Hard TUF ID 869 A2ZSDE

Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with V vertices numbered 0 .. V-1, its edges as a list of pairs, and an integer M. Decide whether every vertex can be given one of M colours so that no edge joins two vertices of the same colour. Return true or false; the colouring itself is not required.

Constraints: 1 ≤ V ≤ 20, 1 ≤ M ≤ V, the graph is simple (no self-loops, duplicates are harmless).

Example 1

V = 4, M = 3, edges = (0,1) (1,2) (2,3) (3,0) (0,2)
answer = true       // colours 0:1, 1:2, 2:3, 3:2 work; 0,1,2 form a triangle so fewer than 3 is impossible

Example 2

V = 3, M = 2, edges = (0,1) (1,2) (2,0)
answer = false      // a triangle needs three different colours

The decision version of graph colouring is NP-complete, so no polynomial algorithm is known; the task is to search cleverly.

Approach 1: Brute force, generate then check

Intuition. A colouring is a function from vertices to {1..M}. Enumerate all M^V of them with a recursion that assigns a colour to vertex 0, then 1, and so on, and when all V vertices have a colour, check every edge. If some complete assignment passes, the answer is true.

Algorithm.

  1. Build a V x V adjacency matrix.
  2. generate(node): if node == V, return valid(color).
  3. For each colour c: set color[node] = c and recurse; if any recursion returns true, propagate it.
  4. valid scans every pair (a, b) with a < b and fails when they are adjacent with equal colours.
static boolean bruteForce(int v, int[][] edges, int m) {
    boolean[][] adj = adjacency(v, edges);
    return generate(0, v, m, new int[v], adj);
}

private static boolean generate(int node, int v, int m, int[] color, boolean[][] adj) {
    if (node == v) return valid(color, adj, v);
    for (int c = 1; c <= m; c++) {
        color[node] = c;
        if (generate(node + 1, v, m, color, adj)) return true;
    }
    return false;
}

private static boolean valid(int[] color, boolean[][] adj, int v) {
    for (int a = 0; a < v; a++) {
        for (int b = a + 1; b < v; b++) {
            if (adj[a][b] && color[a] == color[b]) return false;
        }
    }
    return true;
}

Complexity. Time O(M^V · V²): every assignment is completed and then checked against all pairs. Space O(V²) for the matrix plus O(V) recursion.

Even for V = 10, M = 3 this is about 59 000 full assignments; for V = 20 it is astronomically slow when the answer is false, because a false answer forces the entire space to be enumerated.

Approach 2: Better, backtracking

Intuition. Most of the M^V assignments are doomed early: as soon as two adjacent vertices share a colour, nothing assigned later can fix it. So check the constraint when the colour is chosen, not at the end. Vertex node may take colour c only if none of its already-coloured neighbours has c (isSafe). A whole subtree of M^(V - node - 1) assignments is skipped by one failed check. If no colour fits node, return false so the caller tries its next colour; that return is the backtracking.

Resetting color[node] = 0 after a failed attempt matters because isSafe treats 0 as “not coloured yet”.

Algorithm.

  1. backtrack(node): if node == V, a complete conflict-free colouring exists, return true.
  2. For each colour c in 1..M: if isSafe(node, c), assign it, recurse on node + 1, return true on success, otherwise reset the colour.
  3. Return false when every colour fails.
static boolean better(int v, int[][] edges, int m) {
    boolean[][] adj = adjacency(v, edges);
    return backtrack(0, v, m, new int[v], adj);
}

private static boolean backtrack(int node, int v, int m, int[] color, boolean[][] adj) {
    if (node == v) return true;                      // every vertex coloured without conflict
    for (int c = 1; c <= m; c++) {
        if (isSafe(node, c, color, adj, v)) {
            color[node] = c;
            if (backtrack(node + 1, v, m, color, adj)) return true;
            color[node] = 0;                         // undo
        }
    }
    return false;
}

private static boolean isSafe(int node, int c, int[] color, boolean[][] adj, int v) {
    for (int other = 0; other < v; other++) {
        if (adj[node][other] && color[other] == c) return false;
    }
    return true;
}

Dry run on Example 2 (triangle, M = 2):

node colour tried neighbours’ colours result
0 1 none assign 1
1 1 0 has 1 unsafe
1 2 0 has 1 assign 2
2 1 0 has 1 unsafe
2 2 1 has 2 unsafe, return false
1 (exhausted)   return false
0 2 none assign 2, the same story mirrored
0 (exhausted)   false

Complexity. Time O(M^V · V) in the worst case, since a false instance can still force a large search, but pruning removes every branch that already contains a conflict, which on real graphs is almost all of them. Space O(V²) for the matrix plus O(V) recursion.

Approach 3: Optimal, adjacency lists and symmetry breaking

Intuition. Two refinements make the backtracking noticeably faster without changing its logic.

Gather blocked colours once. isSafe scans a full matrix row for every colour tried, O(V · M) per vertex. With adjacency lists we walk only the actual neighbours once per call and mark their colours in a small blocked array; each colour test is then O(1).

Break the symmetry of colours. Colours have no identity: swapping colour 2 and colour 3 everywhere yields another valid colouring. So whenever the search has only used colours 1..k so far, trying k + 2, k + 3, … for the next vertex is pointless: each of those branches is a relabelling of the k + 1 branch. Restricting the next vertex to colours ≤ maxUsed + 1 cuts the branching factor at the top of the tree from M to 1, then 2, and so on. On false instances, where the whole tree must be exhausted, this alone divides the work by roughly M!.

Two trivial early exits round it off: M ≥ V is always true (give each vertex its own colour) and M = 0 with vertices present is always false.

Algorithm.

  1. Handle V = 0, M ≤ 0 and M ≥ V directly.
  2. Build jagged int[][] adjacency lists from the degree counts.
  3. colourFrom(node, maxUsed): mark colours of coloured neighbours as blocked.
  4. For c from 1 to min(M, maxUsed + 1): skip blocked colours, assign, recurse with max(maxUsed, c), undo on failure.
static boolean optimal(int v, int[][] edges, int m) {
    if (v == 0) return true;
    if (m <= 0) return false;
    if (m >= v) return true;                         // every vertex can simply get its own colour
    int[] degree = new int[v];
    for (int[] e : edges) {
        degree[e[0]]++;
        degree[e[1]]++;
    }
    int[][] adj = new int[v][];
    for (int i = 0; i < v; i++) adj[i] = new int[degree[i]];
    int[] fill = new int[v];
    for (int[] e : edges) {
        adj[e[0]][fill[e[0]]++] = e[1];
        adj[e[1]][fill[e[1]]++] = e[0];
    }
    return colourFrom(0, v, m, new int[v], adj, 0);
}

private static boolean colourFrom(int node, int v, int m, int[] color, int[][] adj, int maxUsed) {
    if (node == v) return true;
    boolean[] blocked = new boolean[m + 1];
    for (int nb : adj[node]) if (color[nb] != 0) blocked[color[nb]] = true;
    int limit = Math.min(m, maxUsed + 1);            // colours above maxUsed + 1 are interchangeable with maxUsed + 1
    for (int c = 1; c <= limit; c++) {
        if (blocked[c]) continue;
        color[node] = c;
        if (colourFrom(node + 1, v, m, color, adj, Math.max(maxUsed, c))) return true;
        color[node] = 0;
    }
    return false;
}

Why symmetry breaking is safe. Take any valid colouring and rename its colours in order of first appearance along the vertex order 0, 1, 2, ...: the first vertex gets 1, the next new colour seen gets 2, and so on. Renaming never creates a conflict (equal colours stay equal, different stay different), and the renamed colouring satisfies “each vertex uses a colour ≤ maxUsed + 1”. So if any valid colouring exists, one that the restricted search can find exists too.

Complexity. Worst-case time is still exponential, O(M^V) in the loosest bound, but with the top levels of the tree collapsed and O(deg) work per node instead of O(V · M). Space O(V + E) for the lists, O(V + M) for color and blocked, O(V) recursion.

Edge cases and pitfalls