The graph (vertex) coloring problem (GCP) consists in finding an assignment of colors to vertices of a graph in such a way that no adjacent vertices receive the same color. Graph coloring problems arise in many real life applications like register allocation, air traffic flow management, frequency assignment, light wavelengths assignment in optical networks and timetabling. More formally, let G = (V, E) be an undirected graph, with V being the set of |V| = n vertices and E being the set of edges. A k-coloring of G is a mapping ϕ : V → Γ, where Γ = 1, 2,…, k is a set of |Γ| = k integers, each one representing a color. A k-coloring is feasible or proper if for all [u, v] ∈ E it holds that ϕ(u) = ϕ(v); otherwise it is infeasible. If for some [u, v] ∈ E it is ϕ(u) = ϕ(v), the vertices u and v are in conflict. A feasible k-coloring in which some vertices are uncolored is said to be a partial k-coloring.
The GCP can be posed as a decision or as an optimization problem. In the decision version, also called the (vertex) k-coloring problem, the question to be answered is whether for some given k a feasible k-coloring exists. The optimization version of the GCP asks for the smallest number k such that a feasible k-coloring exists; for a graph G, this number is called the chromatic number χG.
For some graphs the chromatic number is known. A famous example is the four color theorem: if a graph is planar then it admits a feasible 4-coloring. However, deciding for a planar graph whether it also admits a 3-coloring has been shown to be an NP-complete problem. For general graphs it remains NP-complete and consequently the chromatic number problem NP-hard (Karp 1972).
A famous chess puzzle asks to dispose n queens on an n × n chessboard such that none of them is able to attack any other using the standard chess queen’s moves. Thus, a solution requires that no two queens share the same row, column, or diagonal. Derived from this puzzle, the n2 queen puzzle asks to dispose in a n × n chessboard n × n queens subdivided into n subgroups such that no two queens belonging to the same group can attack each other. See Figure 1 for an example, where queens are represented by the integers 0, … , n−1 and each integer indicates a queen group.
The n2 has a solution whenever (n mod 6) ≡ 1 or 5. This condition is sufficient. It is also necessary when n < 12. Thus none of the n2 queen problems with n = 2, 3, 4, 6, 8, 9 have solution, while for n = 5 and n = 7 a feasible solution is reported in Figure 1. For n ≥ 12 counterexamples have been found, eg, for n = 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 32, that are solvable despite of the fact that the condition does not hold.
0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1
0 1 2 3 4 5 6 5 6 0 1 2 3 4 3 4 5 6 0 1 2 1 2 3 4 5 6 0 6 0 1 2 3 4 5 4 5 6 0 1 2 3 2 3 4 5 6 0 1
This format consists of a file in which each line begins with a letter that defines the content of the line. The legal lines are:
c Comment: remainder of line ignored.
p Problem: is of form:
p edge n m where n is the number of vertices (to be
numbered 1..n) and m the number of edges.
e Edge: is of the form e n1 n2 where n1
and n2 are the endpoints of the edge.
\n (new line) has to
be printed. Colors start from 1 and the first color in the column
represents the color assigned to vertex 1. All vertices must receive
a color, if your solution has uncolored vertices use a dummy color
for them.These are a few practical issues that it is worth knowing in preparation of the exam.
The project will be handed in electronically. The program implementation must be handed in within the given deadline. This is done by submitting through the Blackboad system an archive thus organized:
Main directory:
CPRN/
where CPRN is the student’s CPR number (eg, 030907-4089) and content:
CPRN/README
CPRN/doc/
CPRN/src/
The directory doc may contain the written report, that will be
the main source for the evaluation of the project. The report has to be
kept anonymous. The file README reports the name of the student and the
manual for the compilation of the program. The directory src
contains the source files, which may be in Coment, C, C++, Java or python. If
needed a Makefile can be included either in the root directory or in
src. After compilation the executable must be placed in
src. For java programs, a jar package can also be submitted.
Programs must work on IMADA’s computers under Linux Ubuntu operating system and with the compilers and other applications present on IMADA’s computers. You are free to develop your program at home, but it is your own responsibility to transfer the program to IMADA’s system and make the necessary adjustments such that it works at IMADA.1 The Comet version is assumed to be the last one available.
Your program will be run by typing in
the directory CPRN/src/:
gcp -i INSTANCE -t TIME -s SEED -o OUTPUT
For example:
gcp -i queen8_8.col -o queen8_8.sol -t 300 -s 1 will run
the program on the instance queen8_8.col opportunely
retrieved from the given path for 300 seconds with random seed 1 and
write the solution in the file queen8_8.sol.
It is advisable to have a log of algorithm activities during the
run. This can be achieved by printing on the standard error or in a
file (which maybe determined with a option -o filename) further
information. A suggested format is to output a line whenever a new
best solution is found containing at least the following pieces of
information:
best 853 col 10 time 0.000000 iter 0 par_iter 0