Hey. Graph coloring is nothing but a simple way of labelling graph components such as vertices, edges, and regions under some constraints. For our problem, we will be considering the vertex coloring variation where no two adjacent vertices are colored with minimum number of colors. This number is called the chromatic number and the graph is called a properly colored graph. The k-coloring of the graph is an assignment of colors to each vertex that meets the above constraints and uses exactly k distinct colors in the coloring. Finding the minimum value of k such that a coloring exist is the problem of interest to us.
The senate committee scheduling problem can be reduced to a graph coloring problem in the following manner. We construct a graph G: Each committee is a vertex. An edge is placed between two vertices if the corresponding committees share a member. We can note that if there exists a k-coloring of this graph, the committee meetings can be scheduled using k time slots. We can simply assign each time slot a color and since each vertex is colored, we get a time slot for each vertex i.e. committee. There can be no conflicts as if any two committees have the same time slot (color), they will not have any common members otherwise there would be an edge between the vertices and by the restriction, the coloring is not valid.
Now, we need to find the minimum k. The importance of finding the minimum is shown below in the figure:
This left image is a 2-coloring of the graph while the right image is a 4-coloring of the same graph. Now, if we interpret the graph in the context of our problem, the 2-coloring uses 2 time slots while the right uses 4. In the 4-coloring, while committees 1 and 2 are in a meeting at a time slot red, the remaining committees are sitting idle which is a waste of senator’s time. Scheduling as many meetings as possible in parallel is the goal. Hence, we want to find the minimum value k can take for out committee graph.
Algorithms
The vertex coloring problem is NP-complete. It can be shown by reducing the 3SAT problem to this problem. This means that there is no known polynomial time algorithm for this problem.
Brute-force search for a k-coloring considers each of the kn assignments of k colors to n vertices and checks for each if it is legal. To compute the chromatic number and the chromatic polynomial, this procedure is used for every k=1, …, n-1, impractical for all but the smallest input graphs. In our case of 16 committees, the worst case is if every member is on every committee, which means we would run our algorithm on all values of k from 1 to 16. This would mean in the worst case looking at different colorings which is computationally intractable. We can see that for larger values than 16, this value increases very fast.
We can improve upon this naïve method using backtracking. We assign each vertex a color that does not clash with any of its neighboring vertex’s color and repeat the process until we either finish coloring all vertices or have no valid colors left to assign. This avoids looking at coloring where there is more than one point of conflict significantly improving the run time. This method is still exponentially slow in the worst case and even after several heuristics and optimizations, it is still intractable for large graphs. For the purposes of our problems, however, this method is feasible.
