The class scheduling problem at FCIH and Graph Theory !

The graph scheduling problem in FCIH apparently is not easy to solve. There is many classes, many subjects, student-subject relationship is complicated as it is fine-grained after the credit hours system has been deployed. This result in the schedule being unstable and modified a lot. In this article we seek to model this problem using Graph Theory and see possible solutions, or at least know the exact reason for the problem and the absolute minimum number of resources (time slots, rooms, etc.) needed.

Lets say that our undirected graph consists of vertices representing subjects, and edges representing student-subject relationship. In particular an edge $(i,j)$ is present between subjects $i$ and $j$ is there is a student taking both subjects.

We are going now to assign each vertex a "label" or a "color" representing its time slot (e.g. color$(i)=$ "4th time slot in Monday". We put a restriction that two neighboring vertices (i.e. having an edge between them: a student is taking them both) cannot have the same color; because the student taking both can not attend more than one subject in a time slot. This is the graph vertex coloring problem: given a graph, color its vertices such that no neighboring vertices have the same color. The trivial solution is to give each vertex a unique color. But this is not an interesting solution because you have limited number of color (time slots) and many subject; usually more than the number of time slots.

We might be interested in minimizing the number of colors used. The minimum number of colors needed to color a graph is called the graph's chromatic number, and computing that number is an NP-complete problem, and so there is no efficient algorithm to solve it exactly in the worst case unless P=NP. We may be interested though in a way to approximate it, there is an algorithm to approximate the chromatic number within a multiplicative factor. Notice that knowing the minimum number of colors doesn't mean we found such a coloring.