Graph Coloring Algorithm - Assign color

Question

I have here a function in a graph coloring algorithm which assigns color to a number of courses. But it chooses randomly, and I'd like to improve the algorithm and assign color more efficiently than picking one at random based on the available colors.

In this function, N is the number of time schedules.

void create_schedule(int **graph, list *courses, int numcourses){
    int i, j, k, col=0;
    for(i=0; i<numcourses; i++){
        for(j=0; j<N; j++){
            for(k=0; k<i; k++){
                if(graph[i][k] > 0 && courses[k].color == j) break;
            }
            //color j was not yet chosen by adjacent nodes
            if(k >= i){
                courses[i].color = j;
                break;
            }
        }
        //if there is no color available, choose randomly
        if(j >= N){
            col = rand()%N;
            courses[i].color = col;
        }
    }
}

An explanation would be great.

Your question is unclear. What do you mean by "assign color more efficiently than giving it randomly based on what color is available" what do you mean "efficiently" here? You want it to run faster? What speed up are you expecting and where are you expecting you can achieve it? — amit
And you are aware this problem is NP-Complete? So an optimal solution is going to take exponential time to achieve (unless P=NP, which is unlikely)? — amit
Yes. As long as I minimize the colors used. I care less about the time :) — CrazyGirl
What is approximately the size of N? You might not "care for time" but for lage enough N (say, N>40) - you are unlikely to ever be able to find an optimal solution unless you own a very powerful cluster. — amit

amit amit · Accepted Answer · 2015-05-06T08:33:44

First, let's define the problem canColor(graph, k) - it will answer true if and only if you can do a graph coloring to graph using k colors.

Pseudo code for canColor:

canColor(graph, k):
   if graph is completely colored:
        return checkIfColoringValid(graph)
   v = first uncolored vertex
   for each i from 1 to k (inclusive)
       color v with color i
       //can add optimization here to trim upfront unsuccesful results
       res = canColor(graph,k)
       if res == true:
           return true
   //no answer found
   uncolor v (mark it as color[v] = 0)
   return false

The above is the decision problem of graph coloring.

Now, we need to use it to find the optimal coloring.
Note that if canColor(graph,k) == true, then also canColor(graph,k+1) == true

This means, you have a metaphoric array of answers, 0,0,..0,1,1,...,1, once there is a solution for some k, all values of k after it will also have a solution. This metaphoric array is sorted, so you can apply binary search on it (where instead of accessing the array, you calculate answer for canColor(graph,k) each time), to get the optimal value of k - the number of colors you can use.

Graph Coloring Algorithm - Assign color

1 Answers