what is the graph coloring problem?
In the graph coloring problem, we are tasked with assigning colors to each node in a graph in such a way that no two adjacent nodes share the same color. This concept is akin to coloring a map where neighbouring regions should have different colors. By solving this problem, we can unlock powerful solutions for a variety of graph-related challenges
Consider the following illustration of a graph:
In this example, each circle represents a node, and the lines connecting them represent edges. Now, let’s explore different ways to color this graph:
In this example, each circle represents a node, and the lines connecting them represent edges. Now, let’s explore different ways to color this graph:
Based on the two possibilities of coloring a graph, it’s evident that we require a minimum of two colors to ensure that no two adjacent nodes share the same color, thus satisfying the constraint.
Through the process of graph coloring, we’ll explore how this seemingly simple task can provide an easy solution to a complex problem.
Problem
Note: The problem was taken from codesignal a platform like leetcode
You are the head zookeeper at a large zoo. You’ve been contacted by schools in the area that want to bring in classes so that students can feed the animals. The animals can only be fed once a day, so no two classes can come on the same day if they want to feed the same animals.
You have a list classes, such that classes[i] is a list of animals that the ith class wants to feed. Classes i and j cannot come on the same day if an animal in classes[i] also appears in classes[j] (for i ≠ j). Your job is to determine the minimum number of days you would need to have all the classes come to feed the animals if they can all come within 5 days. If it isn’t possible for all the classes to come within 5 days, return -1 instead.
Examples
For classes = [[“Tiger”, “Lima”, “Frog”], [“Tiger”, “Zebra”,”Lion”], [“Tiger”, “Rabbit”], [“Emu”, “Zebra”, “Rabbit”]], the output should be
solution(classes) = 3.
Classes 0, 1, and 2 all want to feed the Tiger, so they have to come on different days. Class 3 cannot come on the same day as class 1 (because of the Zebra) or class 2 (because of the Rabbit), but they can come on the same day as class 0. Therefore it only takes 3 days for all the classes to visit the zoo.
For classes = [[“Tiger”, “Lima”, “Frog”], [“Tiger”, “Zebra”, “Lion”], [“Tiger”, “Rabbit”], [“Lima”, “Zebra”, “Rabbit”]], the output should be
solution(classes) = 4.
Each class has to come on a separate day, because every pair of classes has at least one animal in common.
For classes = [[“Lion”, “Emu”], [“Giraffe”, “Peacock”], [“Lima”], [“Tiger”, “Cheetah”, “Slugs”], [“Snakes”, “Sealion”]], the output should be
solution(classes) = 1.
No classes have animals in common, so they can all come on the same day.
Now to solve the problem, my initial thought was to
try a recursive backtracking approach, In this method, the recursive function takes two arguments: currentClassIdx, which represents the index of the class currently being processed, and days, an array of sets where each set represents the animals to feed on the ith day. During each recursive call, we have a few options to consider: we can either dedicate an entire new day to this class by appending a new set to days array with the animals to feed, or we can try to merge it with existing days if there are no common animals. We’ll choose the option that leads to the minimum number of days. The base case is reached when we’ve processed all the classes, indicated by currentClassIdx being out of bounds, at which point we return the length of the days array. This approach is pretty straightforward and easy to understand. Let’s take a closer look!
Brute force Solution
classes = [set(x) for x in classes]
def minimumDaysToCoverAllClasses(currentClassIdx, days):
if len(days) > 5:
return float(‘inf‘)
if currentClassIdx >= len(classes):
return len(days)
res = float(‘inf‘)
currentClassAnimals = classes[currentClassIdx]
# new day for this class
days.append(currentClassAnimals)
res = min(res, minimumDaysToCoverAllClasses(currentClassIdx+1, days))
days.pop()
# try merging this class into existing days
for i, animals in enumerate(days):
# no common animals
if animals.isdisjoint(currentClassAnimals):
days[i] = animals.union(currentClassAnimals)
res = min(res, minimumDaysToCoverAllClasses(currentClassIdx+1, days))
# backtrack
days[i] = animals
return res
days = []
currentClassIdx = 0
daysRequired = minimumDaysToCoverAllClasses(currentClassIdx, days)
if daysRequired == float(‘inf‘):
return –1
return daysRequired
The time complexity of the above solution is a bit tricky to calculate and get it exact but it would definitely be something greater than exponential O(n!) , so can we do better?
This is where the graph coloring can be used , it’s hard to see the connection at first I was not able to find the solution and after some time and went through the solutions to find the graph coloring approach solution , once I learnt about it I was amazed that such a complex problem can be solved easily with graph coloring algorithm so decided to share it here, now let us have a look at the graph coloring algorithm
Graph coloring Solution
We will represent each class as a node and if there is common animal to feed between 2 classes then there is a edge between those 2 nodes
Example:
For classes = [[“Tiger”, “Lima”, “Frog”], [“Tiger”, “Zebra”,”Lion”], [“Tiger”, “Rabbit”], [“Emu”, “Zebra”, “Rabbit”]]
Classes 0, 1, and 2 all want to feed the Tiger, so there is an edge between these 3 classes or nodes.
Class 3 has an edge to class 1 (because of the Zebra) and class 2 (because of the Rabbit).
For the above graph we need at least 3 colors to color the graph to satisfy the constraint of no 2 adjacent nodes have the same color, one possible way to color the graph is shown below
It does not matter what colors we choose we just need to find the minimum colors needed to color the graph while ensuring that no 2 adjacent nodes have the same color or in other words minimum days required (each day represents a color) to cover all the classes satisfying the constraint of no 2 classes can come on the same day if they have a common animal to feed.
we will start solving the problem by converting the given information to a graph and once we have a graph representing the above information, we can start coloring the graph to see how many minimum days required to cover all the classes.
As the problem states if the minimum days is less than 5 we return it else -1 , we will add a condition to achieve this but the idea remains the same we are trying to find minimum colors required to color the graph such that no 2 adjacent nodes have the same color or the minimum days required to cover all the classes such that no 2 classes come on same day, here each day represents a color. I hope you are able to see the connection I am trying to explain, now let’s have a look at the code
g = [[] for _ in range(len(classes))]
for u, c1 in enumerate(classes):
for v, c2 in enumerate(classes):
# check if 2 classes have a common animal and add the edge
if u != v and set(c1) & set(c2): g[u].append(v)
return solve(g, 0, [0 for _ in range(len(g))])
# color node u in each recursive call
# once all the nodes are colored count the colors it took to color all the nodes
def solve(g, u, colors):
if u == len(g): return max(colors)
# check the adjacent neibhours colors, we can’t use those colors
used = set(colors[v] for v in g[u])
# choose a color for this node out of available colors
for color in [c for c in range(1, 6) if c not in used]:
colors[u] = color
colorsRequired = solve(g, u + 1, colors)
if 0 <= colorsRequired < 6: return colorsRequired
return –1
The time complexity of the above solution is O(5^c) where c is number of classes as you can see this solution is much more efficient.
Conclusion
The key insight lies in recognizing how to represent the problem information as a graph. Once we have this representation, coloring the graph using techniques like recursion and backtracking becomes straightforward. This approach allows us to determine either the minimum days required or the minimum number of colors needed to satisfy the problem constraints.
Understanding how to translate real-world scenarios into algorithmic representations is crucial. Once we grasp this conceptual framework, solving similar problems becomes more manageable and intuitive.
