Autonomous University of Nuevo Leon
Faculty of Mechanical and Electrical Engineering
Selected Topics of Optimization
Heuristic : constructive + local search
Name ID Carrer
Edwin Patricio Castillo Estrada 1750368 ITS
Teacher: Maria Angelica Aguilar Salazar
Semester: January – June 2022
Date 06 April 2022
1. General description of the studied problem
Graph coloring problem is to assign colors to certain elements of a graph subject to certain
constraints.
The problem is, given m colors, find a way of coloring the vertices of a graph.
The constraints in a graph, no two adjacent vertices, adjacent edges, or adjacent regions are
colored with the same colors.
The objective is to minimize the number of colors while coloring a graph. The smallest
number of colors required to color a graph G is called its chromatic number of that graph.
Graph coloring problem is a NP Complete problem.
Chromatic Number: The smallest number of colors needed to color a graph G is called its
chromatic number. For example, the following can be colored minimum 2 colors.
2. Description and pseudo code of the constructive heuristic
and local search
Welsh Powell Algorithm (Constructive Heuristic)
In graph theory, Welsh Powell is used to implement graph labeling; it is an assignment of
labels traditionally called "colors" to elements of a graph subject to certain constraints.
The vertices are ordered according to their degrees, the resulting greedy coloring uses at most
one more than the graph’s maximum degree.
Steps
1. Find the degree of each vertex .
2. List the vertices in order of descending valence .
3. Colour the first vertex in the list.
4. Go down the sorted list and color every vertex not connected to the colored vertices
above the same color then cross out all colored vertices in the list.
5. Repeat the process on the uncolored vertices with a new color-always working in
descending order of degree until all in descending order of degree until all vertices are
colored.
Pseudo code
The idea is to number the vertices by descending order and then, starting with c(v1) = 1, visit
the remaining vertices in order of the list, assigning them the lowest-numbered colour not
yet used for a neighbor.
Input G= (V, E) number of vertex and adjacency matrix [i][j] of the graph
Output: A vertex coloring for graph G (chromatic number)
Adjacency matrix[i][j]
n=number of vertex
C=colors {0, 1, 2, 3….}[ ]
vi,vj =the vertex to be colored, being i and j neighbors. (adjacent to each other) c(i),c(j)
Begin
Main
Sort n desc by degree //Find the degree of each vertex
Let ln ← [n] //Store the vertex list in array by descending order
Input n //number of vertices of the graph
Input adjacency matrix of the graph
Call chromatic number function //parameters “n” and adjacency
matrix[i][j]
Color ← 0 //Assign the first color to the first vertex
Chromatic number ← 1//Equals to 1 since we already use one color
New color ← 0 // New color for the graph
For i=1 n
For j=0 i
If adjacency matrix[i][j]==1
Then
New color = 1
Else
Color[i] =Color[j] //We can use the same color
New color=0
End If
If new color = 1
Then
Chromatic number = chromatic number + 1
Color[i] =Chromatic number
End If
Repeat the process with the remaining vertex according to the list.
Return Chromatic number
END
Backtracking algorithm “m” coloring (Local search)
The idea is to assign colors one by one to different vertices,
starting from the vertex 0.
Before assigning a color, check for safety by considering already
assigned colors to the adjacent vertices i.e check if the adjacent
vertices have the same color or not.
If there is any color assignment that does not violate the
conditions, mark the color assignment as part of the solution. If
no assignment of color is possible then backtrack and return
false.
Pseudo code
Input G= (V, E) number of vertex of the graph (n) and the Adjacency matrix[i]
[j]
Output: A path for the graph using the available colors (m)
n=number of vertex
m=colors {0, 1, 2, 3….} //how many colors can we use for coloring the graph
Steps:
1. Assign a color to a vertex (1 to m).
2. For every assigned color, check if the configuration is safe, (by checking
whether any of its adjacent vertices are colored with the same color).
3. Confirm whether it is valid to color the current vertex with the current
color.
4. If yes then color it and otherwise try a different color.
5. Check if all vertices are colored or not.
6. If not then move to the next adjacent uncolored vertex.
7. If no other color is available or color assignment is not possible then
backtrack (i.e. un-color last colored vertex). and return false
Begin
Main
Input number of vertex (n)
Input the adjacency matrix of the graph (Adj_matrixII)
Input m colors to try to color the graph (m)
Function to validate safety to color a graph or not(Safe)
Begin
for all vertices v of the graph, do
if there is an edge between v and i, and col = colorList[i],
then
return false
done
return true
End Function
Function to color the vertices (graphColoring)
Begin
if all vertices are checked, then
return true
for all colors col from available colors, do
if isValid(vertex, color, col), then
add col to the colorList for vertex
if graphColoring(colors, colorList, vertex+1) = true, then
return true
remove color for vertex
done
return false
End Function
Print solution( color[]) //Here print the path with the assigned
colors to the graph if exists a possible solution
End
3. Experimental results
Instances
Description
The instances used in this problem are a combination of data obtained by the web and
random graphs generated for programs, webpages and for the team during the last
presentations of the heuristic.
Some graph where take by examples of videos in the web where it explain the
heuristic and the problems itself of graph coloring.
A webpage was used for creating multiple graphs in order to test the heuristics
proposed in this activity.
https://graphonline.ru/es/
https://www.youtube.com/watch?v=-icmP32FphE&t=823s
https://www.gatevidyalay.com/graph-coloring-chromatic-number/
Instance 1
Chromatic number = 2 Feasible solution = NO
Local search solution = Infeasible
Instance 2
Chromatic number = 3 Feasible solution = YES
Local search solution = Infeasible (2 colors)
Instance 3
Chromatic number = 4 Feasible solution = YES
Local search solution = Infeasible (3 colors)
Instance 4
Chromatic number = 1 Feasible solution = NO
Local search solution = Infeasible
Instance 5
Chromatic number =2 Feasible solution = NO
Local search solution = Infeasible
Instance 6
Chromatic number =2 Feasible solution = NO
Local search solution = Infeasible
Instance 7
Chromatic number =2 Feasible solution = YES
Local search solution = Infeasible (1 color)
Instance 8
Chromatic number =2 Feasible solution = NO
Local search solution = Infeasible
Instance 9
Chromatic number =5 Feasible solution = YES
Local search solution = Infeasible (4 colors)
Instance 10
Chromatic number =3 Feasible solution = YES
Local search solution = Infeasible (2 colors)
Instance 11
Chromatic number =2 Feasible solution = NO
Local search solution = Infeasible
Instance 12
Chromatic number =3 Feasible solution = YES
Local search solution = Infeasible (2colors)
Instance 13
Chromatic number =4 Feasible solution = YES
Local search solution = Infeasible (3colors)
Instance 14
Chromatic number =4 Feasible solution = YES
Local search solution = Infeasible (3colors)
Instance 15
Chromatic number =3 Feasible solution = YES
Local search solution = Infeasible (2colors)
Instance 16
Chromatic number =1 Feasible solution = NO
Local search solution = Infeasible
Instance 17
Chromatic number =1 Feasible solution = NO
Local search solution = Infeasible
Instance 18
Chromatic number =2 Feasible solution = YES
Local search solution = Infeasible (1 color)
Instance 19
Chromatic number =2 Feasible solution = NO
Local search solution = Infeasible
Instance 20
Chromatic number =4 Feasible solution = YES
Local search solution = Infeasible (3 colors)
Analysis
Based on the results obtained through the instances.
It can be seen that the percentage of successes of the heuristic
model was of 55% with 11/20 instances with a feasible solution
For the local search process I could see that removing a color (k-
1) from the chromatic number at all cases did not reach a
feasible solution.
The chromatic number obtained with the greedy algorithm was
the most optimal solution in all cases where a solution with this
algorithm existed in the first place.
The algorithm for the local search works correctly, but removing
a color from the chromatic number obtained by the heuristics of
the greedy algorithm did not reach a more optimal solution
than the previous one.
Conclusion
After carrying out different tests with several instances for the
heuristics and the subsequent local search for a better solution.
I can say that in all cases where there is a feasible solution
obtained by the greedy algorithm heuristic … This was the best.
Trying to perform a local search with M-1 number of colors to
the previously solved graph. It resulted in an infeasible solution.
Due to the dimensions of the graphs and the complexity of my
heuristics(which is very simple).
I could not support a large graph, so it had to resort to graphs of
medium or small sizes, in which I could obtain a solution with
which to perform a local search.
The advantage of my first heuristic to obtain a chromatic
number was its simplicity and its ability to produce a feasible
result.
For the local search use the algorithm of m colors to be able to
try to find a better solution than the one obtained previously.
Its advantage was the instructions and parameters that it took
into account to make a decision on the coloring of the graph.
This procedure yields more feasible solutions unlike the greedy
algorithm in which decisions are made on the spot without
taking into consideration other aspects.
However, for the instances that used the greedy algorithm, in
the cases that could obtain a solution, this was always the most
optimal. Therefore, the local search could not be carried out to
obtain a better solution.
The disadvantage of my heuristics was the poor ability of my
program to understand data.
An example of this is that I could see that in any graph that
contained a triangle between its vertices, it had a greater
probability of not obtaining a solution in the first place.
And without an initial solution the local search for a more
optimal solution cannot be carried out.
I hope to be able to fix this problem and in this way be able to
introduce more data to my heuristics for its subsequent
processing and thus obtain a feasible solution for large graphs.
