Greedy and Backtracking Algorithm Comparison in Graph Coloring Problem

Abstract. 

Graph Coloring is a technique of coloring vertices on a graph so that no neighboring nodes have the same color. Usually this is also associated with minimal use of color. Graph coloring techniques are one of the most interesting and well-known subjects in the field of graphics. The theory of graph coloring has been developed with various algorithms to solve it, one of them is Greedy Algorithm and Backtracking Algorithm. In this blog we do analytic design algorithm to solve graph coloring using greedy algorithm and backtracking algorithm and find the ‘m’ (minimum) colors if possible. 

The graph coloring problem is a practical method of representing many real world problems including time scheduling, frequency assignment, register allocation, and circuit board testing. The most important fact that makes graph coloring exciting is that finding the minimum number of colors for an arbitrary graph is NP-hard. This blog implements Greedy algorithms and Backtracking algorithm to find a solution for the graph coloring problem. Greedy algorithm is very fast but sometimes greedy algorithm don’t give a optimal solution to minimal color in the graph. I think there is no algorithm faster than greedy algorithm to solve graph coloring problem. Backtracking is not so fast but backtracking algorithm always give solution how graph can be colored with ‘m’ colors if possible.

1. Introduction 

A graph is a mathematical structure consisting of two sets V(vertices) and E(edges). Proper coloring is an assignment of colors either to the vertices of the graphs, or to the edges, in such a way that adjacent vertices / edges are colored differently.

As its name, Graph Coloring is used to solve the coloring of graph, especially the vertices or the edges. Besides coloring the graph, graph coloring also used to solve finding minimum color needed to color a graph, which called as chromatic number and notated as m.

The most applications involving vertex coloring are concerned with determining the minimum number of colors required under the condition that the end points of an edge cannot have the same color. A proper vertex coloring of a graph is an assignment from its vertex set to a color set that the end points of each edge are assigned two different colors. The chromatic number of a graph G, denoted by χ(G), is the minimum number of different colors required for a proper vertex coloring of G. Applications of vertex coloring include scheduling, assignment of radio frequencies, separating combustible chemical combinations, and computer optimization. 

In our blog, we use 2 algorithms, which are greedy algorithm and backtracking algorithm to solve the graph coloring problem. Those two algorithms produce colored nodes, in which results has their own chromatic number (i.e. minimum color needed to color the graph) and every adjacent vertex (i.e. vertices that have edges that connect them) has different color. In greedy algorithm, the vertices are sorted based on their degree (i.e. amount of edges that connected to a vertex), and then the vertices are colored based on the order of sorted vertex. Meanwhile in backtracking algorithm, the start point of coloring is set at the first vertex, and then continue to the next vertices.

2. Analysis of Algorithm 

2.1. Greedy Algorithm 

The concept of Greedy Algorithm that used in our project is finding vertex with largest degree and color them with one color. To find vertex with largest degree, the first thing to do is sorting all available vertices based on their degree. After that, the vertex is checked whether it is adjacent to colored vertices or not. If adjacent, the new color will be assigned to the vertex and if not, the vertex the color that will be assigned to the vertex is the same with its non-adjacent vertex. This is done to get the minimum color, which also called chromatic number. However, being too greedy on the first steps may cause problems for later choices forcing the use of unnecessary colors. 

Algorithm:

• Find the degree of each vertex
• List the vertices in order of descending degrees.
• Colour the first vertex with color 1.
• Move down the list and color all the vertices not connected to the coloured vertex, with the same color.
• Repeat step 4 on all uncolored vertices with a new color, in descending order of degrees until all the vertices are coloured.

.2.2. Backtracking Algorithm 

In backtracking algorithm, a vertex is assigned with a color. After that, for every vertex starts from second node, every vertex is checked whether it’s adjacent and has the same color with colored vertices. If so, then the vertex is colored with other color. This process continues until all nodes are colored and recursively done. 

Algorithm:

• Create a recursive function that takes the graph, current index, number of vertices and output color array.
• If the current index is equal to number of vertices. Print the color configuration in output array.
• Assign color to a vertex (1 to m).
• For every assigned color, check if the configuration is safe, recursively call the function with next index and number of vertices
• If any recursive function returns true break the loop and return true.
• If no recursive function returns true then return false.

2.3. Time Complexity 

Greedy Algorithm: O(V2 + E) 

Backtracking Algorithm: O(m^V) 

3. Experimental Results 

3.1. Study case

 In our blog, we will use the problem such as: “Given graph with n amount of vertex and each vertex has their own neighbors. How much is the minimum color needed and what’s the result of graph coloring using Greedy and Backtracking Algorithm? Which algorithm is faster and more effective?”

3.2. Experimental Results 

The experimental results are shown by the graph below:

 

Based on the graph above, the result of greedy algorithm is always faster than Backtracking Algorithm. Average time of Greedy Algorithm is 0.171875 while Backtracking Algorithm’s average time is 0.296875. Also, the more nodes in the graph, the more time needed to solve the problem.

Greedy Algorithm Code

# class to represent a graph object
class Graph:
        # Constructor
        def __init__(self, edges, N):
                self.adj = [[] for _ in range(N)]
                # add edges to the undirected graph
                for (src, dest) in edges:
self.adj[src].append(dest)
self.adj[dest].append(src)
# Function to assign colors to vertices of graph
def colorGraph(graph):
        # stores color assigned to each vertex
result = {}
        # assign color to vertex one by one
for u in range(N):
                # set to store color of adjacent vertices of u
# check colors of adjacent vertices of u and store in set
assigned = set([result.get(i) for i in graph.adj[u] if i in result])
                # check for first free color
color = 1
for c in assigned:
if color != c:
break
color = color + 1
                # assigns vertex u the first available color
        for v in range(N):
print("Color assigned to vertex", v, "is", colors[result[v]])
# Greedy coloring of graph
if __name__ == '__main__':
      # Add more colors for graphs with many more vertices
colors = ["", "BLUE", "GREEN", "RED", "YELLOW", "ORANGE", "PINK", "BLACK", "BROWN", "WHITE", "PURPLE"]
      #  of graph edges as per above diagram
edges = [(0, 1), (0, 4), (0, 5), (4, 5), (1, 4), (1, 3), (2, 3), (2, 4)]
      # Set number of vertices in the graph
N = 6
       # create a graph from edges
graph = Graph(edges, N)
       # color graph using greedy algorithm
colorGraph(graph)

result[u] = color

OUTPUT:

Backtracking Algorithm Code

class Graph(): 

def __init__(self, vertices): 

self.V = vertices 

self.graph = [[0 for column in range(vertices)]

for row in range(vertices)] 

# utility function to check if the current color assignment 

# is safe for vertex v 

def isSafe(self, v, colour, c): 

for i in range(self.V): 

if self.graph[v][i] == 1 and colour[i] == c: 

return False

return True

# A recursive utility function to solve m 

# coloring problem 

def graphColourUtil(self, m, colour, v): 

if v == self.V: 

return True

for c in range(1, m + 1): 

if self.isSafe(v, colour, c) == True: 

colour[v] = c 

if self.graphColourUtil(m, colour, v + 1) == True: 

return True

colour[v] = 0

def graphColouring(self, m): 

colour = [0] * self.V 

if self.graphColourUtil(m, colour, 0) == None: 

return False

# Print the solution 

print("Solution exist and Following are the assigned colours:")

for c in colour: 

print(c); 

return True

# Driver Code 

g = Graph(4) 

g.graph = [[0, 1, 1, 1], [1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0]] 

m = 3

g.graphColouring(m) 

OUTPUT:

EXAMPLE

Conclusion 

From the trials we can conclude that greedy algorithm is faster but less efficient, sometimes greedy give optimal solution. Greedy algorithm is suggested for low data or a little of vertex. Backtracking algorithm is slower but more efficient, backtracking always give optimal solution. Backtracking is suggested for a huge data or a large number of vertex. 

The minimum color needed is based on the connection of vertex, amount of vertex and what algorithm that we use. Lower the Chromatic number, more optimum is the solution.