M-Coloring Problem Editorial

Practice Problem Link: M-Coloring Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given an undirected graph with n nodes and an integer m. Find if it is possible to color all the vertices of the graph using at most m colors, such that no two adjacent vertices have the same color.

Naive Approach

We can use recursive brute force to solve this problem naively. We try to generate all the possible configurations of colors. Then we check if any node and its neighbors have their colors equal. Once we find a valid configuration, we can return true. Else, after exhaustively searching for all the possible configurations we return false.

Analysis

• Time Complexity: O(mⁿ)
• Space Complexity: O(n)

Implementation

C++

bool isSafe(vector<vector<int>> adjMatrix, int color[], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if(adjMatrix[i][j] && color[j] == color[i]) {
				return false;
			}
		}
	}
	return true;
}
bool colorGraph(vector<vector<int>> adjMatrix, int m, int index, int color[], int n) {
	if(index == n) {
		return ((isSafe(adjMatrix, color, n));
	}
	for(int j = 1; j <= m; j++) {
		color[index] = j;
		if(colorGraph(adjMatrix, m, index + 1, color, n)) {
			return true;
		}
		color[index] = 0;
	}
	return false;
}
bool isColoringPossible(vector<vector<int>> adjMatrix, int m) {
	int n = adjMatrix.size();
    int color[n];
	memset(color, 0, sizeof(color));
	for(int i = 0; i < n; i++) {
		if(adjMatrix[i][i]) {
			return false;
		}
	}
	return colorGraph(adjMatrix, m, 0, color, n);
}

Java

class Solution {
	boolean isSafe(int[][] adjMatrix, int[] color, int n) {
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if(adjMatrix[i][j] == 1 && color[j] == color[i]) {
					return false;
				}
			}
		}
		return true;
	}
	boolean colorGraph(int[][] adjMatrix, int m, int index, int[] color, int n) {
		if(index == n) {
			return ((isSafe(adjMatrix, color, n));
		}
		for(int j = 1; j <= m; j++) {
			color[index] = j;
			if(colorGraph(adjMatrix, m, index + 1, color, n)) {
				return true;
			}
			color[index] = 0;
		}
		return false;
	}
	boolean isColoringPossible(int[][] adjMatrix, int m) {
    	int n = adjMatrix.length;
		int color[] = new int[n];
		for(int i = 0; i < n; i++) {
			if(adjMatrix[i][i] == 1) {
				return false;
			}
		}
		return colorGraph(adjMatrix, m, 0, color, n);
	}
}

Optimal Approach

We approach the problem with a backtracking-based approach, trying to prune through many impossible cases. The idea is to assign colors to the vertexes one by one starting from vertex 0. Before assignment of the current color, we check if applying the current color is valid, else we backtrack through the configuration to find another valid configuration. If no valid configuration is found, we return false.

Analysis:

• Time Complexity: O(mⁿ) // The average-case complexity will be much improved upon.
• Space Complexity: O(n)

Implementation:

C++

bool isSafe(vector<vector<int>> adjMatrix, int color[], int n, int c, int v) {
	for (int i = 0; i < n; i++) {
		if(adjMatrix[v][i] && c == color[i]) {
			return false;
		}
	}
	return true;
}
bool colorGraph(vector<vector<int>> adjMatrix, int m, int index, int color[], int n, int v) {
	if(v == n) {
		return true;
	}
	for (int j = 1; j <= m; j++) {
		if(isSafe(adjMatrix, color, n, j, v)) {
			color[v] = j;
			if(colorGraph(adjMatrix, m, index, color, n, v + 1)) {
				return true;
			}
			color[v] = 0;
		}
	}
	return false;
}
bool isColoringPossible(vector<vector<int>> adjMatrix, int m) {
	int n = adjMatrix.size();
    int color[n];
	memset(color, 0, sizeof(color));
	for(int i = 0; i < n; i++) {
		if(adjMatrix[i][i]) {
			return false;
		}
	}
	return colorGraph(adjMatrix, m, 0, color, n, 0);
}

Java

class Solution {
	boolean isSafe(int[][] adjMatrix, int[] color, int n, int c, int v) {
		for (int i = 0; i < n; i++) {
			if(adjMatrix[v][i] == 1 && c == color[i]) {
				return false;
			}
		}
		return true;
	}
	boolean colorGraph(int[][] adjMatrix, int m, int index, int[] color, int n, int v) {
		if(v == n) {
			return true;
		}
		for (int j = 1; j <= m; j++) {
			if(isSafe(adjMatrix, color, n, j, v)) {
				color[v] = j;
				if(colorGraph(adjMatrix, m, index, color, n, v + 1)) {
					return true;
				}
				color[v] = 0;
			}
		}
		return false;
	}
	boolean isColoringPossible(int[][] adjMatrix, int m) {
    	int n = adjMatrix.length;
		int color[] = new int[n];
		for(int i = 0; i < n; i++) {
			if(adjMatrix[i][i] == 1) {
				return false;
			}
		}
		return colorGraph(adjMatrix, m, 0, color, n, 0);
	}
}