Assignment 0, Autumn 2012 [pdf format] |
This a series of obligatory assignments that has the goal of preparing the student to the final project. Throughout the assignments you will set up a developing environment, gain practical experience on the methods discussed in class, try your own ideas on a problem different from those discussed in class, and carry out the analysis of experimental results. The content of the assignments will also provide elements for discussion in class. You are encouraged to search feedback among your peers, and ask questions in class related to the assignment. Working in groups is allowed, but since the final project will be individual in order to prepare your tools, you are recommended to develop source code on your own (be aware that not only the idea but also how it is implemented is relevant for the final performance of an algorithm, and performance counts in this course). The submission of the obligatory assignments is individual.
There will be 1+3 obligatory assignments. All assignments 1 to 3 must be
passed in order to be admitted to the final exam. Assignment 0 has a
slightly different character with respect to the others. Since it starts
before the lectures, it will not be strictly obligatory and a missed
submission to assignment 0 will not compromise the possibility to the to
take part in the other assignments and in the final project. Note
however that Assignments 1 to 3 build on Assignment 0 hence it is very
likely that the work for this assignment must be done at some point.
The assignments are focused on the well known Graph Coloring Problem.
The graph (vertex) coloring problem (GCP) asks to find an assignment of colors to the vertices of a graph in such a way that no adjacent vertices receive the same color. See Figure 1 for an example.
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 and the problem is thus called the chromatic number problem.
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 a NP-complete problem. For general graphs it remains NP-complete and, consequently, the chromatic number problem is NP-hard (Karp 1972).
Random graphs are generated by deciding a number of vertices and including an edge between any pair of vertices with probability p. They are typically indicated by Gp In this assignment you will be asked to find feasible colorings that use the fewest possible colors to random graphs with |V|= 1000 and p=0.5.
Five instances of random graphs plus graph with 10 vertices of Figure 1, useful for debugging purposes, are made available here:
The format of the instance files is the following. 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.
A starting skeleton in Java and C++ for reading these instances is available at the course web page:
Feel free to add and remove data structures.
Note that the Java framework is much less tested than the C++ one. It is possible to use other programming languages (eg, python) but there is no skeleton available for those.
Your task is to design, implement and execute an heuristic solution algorithm for the chromatic number problem. An heuristic algorithm is an algorithm that provides good solutions in reasonable time (in this assignment less than one minute) without a proof of optimality.
You must submit your solutions following the instructions below at this web page:
The web page will store all submissions and provide an analysis of results for the assessment of the best algorithm. You can continue to submit new results until the deadline.
Your submission must consist of a single gzip archive with extension
.tgz. The archive must contain the solutions to the 5 instances
of random graphs. When uncompressed via tar xzvf the files must
be found in the same directory. The files must be named with the name of
the instance (without .col extension) and with extension
.sol. The files must be in ASCII format and consist of a single
column of numbers representing the colors to each vertex. Each number
indicates the color for the vertex corresponding to the line number. Both
colors and vertices start at 1. For example:
$ cat marco10.sol 2 3 4 3 2 2 1 ...
indicates that the vertex 1 receives color 2, vertex 2 receives color 3, etc.