CS 215 Homework 4

1. This exercise introduces a greedy algorithm for m-coloring a graph. Below the image is a greedy algorithm for graph coloring.
   1. What is the time complexity of this algorithm?
   2. What coloring does this algorithm output for the graph below?

   Inputs: positive integers n and m, and an undirected graph containing n vertices. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W[i][j] is true if there is an edge between ith vertex and the jth vertex and false otherwise.

   Outputs: An m-coloring of the graph, as an array vcolor indexed from 1 to n (vcolor [i] is the color - integer between 1 and m - assigned to vertex i). In case the algorithm fails to find a solution, no array vcolor is printed. We will assume that vcolor is a global array.

   
       void m_coloring_greedy (int n, int m) 
       {
           set_of_colored_nodes = ∅;        //no nodes are colored yet
           for (int color = 1; color <= m, color++) {      //cycle through all colors
           {
               for (int i not in set_of_colored_nodes) //cycle through all nodes of graph
                   if(promising (i, color)) 
                   {
                       set_of_colored_nodes = set_of_colored_nodes ∪ {i};
                       vcolor(i) = color;
                       if(set_of_colored_nodes is full) 
                       {
                           print vcolor[1] through vcolor[n]; //found solution
                           return;     //exit function
                       }
                   }
           }
       }
   
       bool promising ( int i, int color) 
       {
           bool switch = true;
           for (int j  in set_of_colored_nodes)      //Check if adjacent vertex is this color
           {                            
               if (W[i][j] && color == vcolor[j])
                   switch=false;
           }
           return switch;
       }
       

2. Show that this greedy algorithm does not guarantee an optimal solution by finding a graph such that reordering/renumbering the vertices leads to a result with a different number of colors. (Hint: Use the greedy m-coloring algorithm to color the graph below. Then find a renumbering of the vertices so that the greedy m-coloring algorithm will use fewer colors on the renumbered graph.)
   
3. Describe two practical applications that are representable in terms of the m-coloring problem. You must cite your sources in order to receive credit on this problem.