L16. M-Coloring Problem | Backtracking

1. Problem Statement & Overview

The M-Coloring Problem is a classic graph theory problem solved efficiently using Backtracking. Given an undirected graph and an integer m (representing the maximum number of colors available), our objective is to determine whether the graph can be colored such that no two adjacent vertices share the same color.

• Input: An undirected graph (with n nodes) and an integer m (maximum colors).
• Output: Return true (or 1) if the graph can be successfully colored under the constraint, and false (or 0) otherwise.
• Key Insight: It is not compulsory to use all m colors; m simply represents the maximum upper bound of available colors.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Think of coloring a geographical map of countries or states. A fundamental cartography rule dictates that no two neighboring (adjacent) countries sharing a border can be painted with the same color. If you have a box of m colored pencils, you must systematically assign pencils to each country so that no borders conflict. If you run into a dead end where all available colors clash with your neighbors, you step back (backtrack), erase your previous choice, and try a different color.

3. Naive vs. Systematic Backtracking Approach

• Naive Exhaustive Search: Try every conceivable color combination across all nodes blindly. This approach is inefficient and ignores graph constraints during the process.
• Recursive Backtracking Approach: Process the graph node by node (from index 0 up to n - 1). For the current node, iterate through every available color from 1 to m. Check if the color is safe (i.e., no adjacent node already holds that color). If safe, tentatively assign the color and recursively attempt to color the next node. If the recursive chain succeeds, propagate true. If it fails, backtrack (remove the color) and try the next color.

4. Step-by-Step Flow Walkthrough (Successful Coloring)

Consider a graph with 4 nodes (0 to 3) and m = 3 colors:

5. Step-by-Step Flow Walkthrough (Failed Coloring & Backtracking)

Consider the same graph with m = 2 colors:

6. Complete Java Implementation

import java.util.List;

public class MColoringProblem {

    public boolean graphColoring(List<Integer>[] graph, int m, int n) {
        int[] color = new int[n];
        return solve(0, graph, color, n, m);
    }

    private boolean solve(int node, List<Integer>[] graph, int[] color, int n, int m) {
        // Base case: If we have successfully colored all nodes
        if (node == n) {
            return true;
        }

        // Try every color from 1 to m
        for (int i = 1; i <= m; i++) {
            if (isSafe(node, graph, color, i)) {
                color[node] = i; // Assign color

                // Recurse for the next node
                if (solve(node + 1, graph, color, n, m)) {
                    return true;
                }

                // Backtrack: remove the color if it didn't lead to a solution
                color[node] = 0;
            }
        }

        // If no color can be assigned to this node, return false
        return false;
    }

    private boolean isSafe(int node, List<Integer>[] graph, int[] color, int col) {
        // Check all adjacent nodes
        for (int neighbor : graph[node]) {
            if (color[neighbor] == col) {
                return false; // Adjacent node has the same color
            }
        }
        return true;
    }
}

7. Complete C++ Implementation

#include <iostream>
#include <vector>

using namespace std;

bool isSafe(int node, vector<vector<int>>& graph, vector<int>& color, int n, int col) {
    for (int k = 0; k < n; k++) {
        // Check if there is an edge and the adjacent node has the same color
        if (graph[node][k] == 1 && color[k] == col) {
            return false;
        }
    }
    return true;
}

bool solve(int node, vector<vector<int>>& graph, vector<int>& color, int n, int m) {
    // Base case: all nodes are colored
    if (node == n) {
        return true;
    }

    // Try all colors from 1 to m
    for (int i = 1; i <= m; i++) {
        if (isSafe(node, graph, color, n, i)) {
            color[node] = i;

            // Recursive step
            if (solve(node + 1, graph, color, n, m)) {
                return true;
            }

            // Backtracking step
            color[node] = 0;
        }
    }

    return false;
}

bool graphColoring(vector<vector<int>>& graph, int m, int n) {
    vector<int> color(n, 0);
    if (solve(0, graph, color, n, m)) {
        return true;
    }
    return false;
}

8. Complexity Analysis

Summary and Key Takeaways

• Problem Definition: Determine if an undirected graph can be colored using at most m colors such that no adjacent nodes share a color.
• Recursive State: We process nodes sequentially from index 0 to n - 1.
• Try All Options: At each node, iterate through color choices from 1 to m.
• Safety Validation: Use an isSafe check to guarantee no adjacent neighbor currently holds the candidate color.
• Backtracking Mechanics: If a recursive branch fails downstream, reset color[node] = 0 before trying the next color.
• Base Case: Reaching node index n signifies that all nodes have been validly colored, triggering a successful true return.
• Complexity Trade-off: The worst-case time complexity is exponential ($O(m^n)$), but graph constraints significantly optimize practical execution.