CS29003 Algorithms Laboratory |
Autumn 2013, L-T-P: 0-0-3 |

## Assignment No 4

## Greedy Graph Coloring

Let

G= (V,E) be a (simple undirected) graph. Two types of coloring problems are of importance in graph theory and the study of algorithms.

Vertex coloring:We assign colors to the vertices ofGin such a manner that no two adjacent vertices receive the same color. The objective is to accomplish this task using as few colors as possible.

Edge coloring:We assign colors to the edges ofGin such a manner that no two edges sharing an endpoint receive the same color. Again, the objective is to accomplish this task using as few colors as possible.Both these problems appear to be difficult. Under certain complexity-theoretic assumptions, no polynomial-time algorithms exist to solve these problems. However, given the importance of these problems, we need to solve them. Given that polynomial-time algorithms fail to guarantee optimal solutions, we have to keep ourselves happy with suboptimal solutions. But then, how bad can these suboptimal solutions be? Can they be guaranteed to be within a constant multiple of the optimal solutions? The answer is again

no. Indeed, ifGcontainsnvertices, no polynomial-time algorithm is expected to exist whose solutions are poorer than the optimal solutions by a factor of O(n^{1−ε}) for any ε > 0. Nevertheless, for random graphs, these suboptimal solutions are often not as bad as these pessimistic estimates suggest.In this assignment, you implement a greedy algorithm to solve the vertex-coloring problem. Later, you solve the edge-coloring problem by reducing the problem to the vertex-coloring problem. The assignment has four important parts.

Generate a random graph- The user supplies the number
nof vertices and a probabilityp. Write a function that generates a random graph withnvertices. For each pair (u,v) of distinct vertices, include the edge (u,v) in the edge setEwith probabilityp. This means that for each vertex pair, you generate a random floating-point number in the interval [0,1]. If that random number is ≤p, add the edge joining the vertices, else do not include the edge. Use theadjacency-list representationof the graph. Print the graph (vertices and the neighbors of each vertex).Constructing maximal independent sets in a graph- All vertices that receive the same color must be non-adjacent to one another. Such a set of vertices is called an
independent set. Write a function that, given a graphG, generates a maximal independent set in the graph. A maximal independent set is one with the property that the addition of any remaining vertex to the set destroys the "independent-set" property of the set. Ideally, we like to locate a maximum independent set inG(that is, an independent set of size as large as possible), but this is again a difficult computational problem. What you instead implement is the following greedy algorithm. This algorithm always outputs maximal independent sets (but they need not be maximum).

Initialize Sto the empty set.

Repeat the following three steps so long as the graphGis not empty :

Locate a vertexuof (remaining) minimum degree inG.

AddutoS.

Deleteuand all its neighbors fromG.

ReturnS.By the deletion of a vertex

vfrom a graphG= (V,E), we imply the deletion ofvfrom the vertex setVand the deletion, from the edge setE, of all the edges in whichvis an endpoint. The loop in the above algorithm terminates when all vertices are deleted fromG. In the process,Saccumulates some vertices. By construction, these vertices must form an independent set. Moreover, it must be maximal. The greedy choice ofu(one of minimum degree) is justified because we desire to makeSlarge.Greedy vertex coloring- Write a function to compute a coloring of the vertices of a graph
G. Implement the following greedy algorithm that invokes the function for constructing maximal independent sets multiple times.

Set c= 0.

Repeat the following four lines untilGis empty :

Compute a maximal independent setSinG.

Incrementc(use the next color).

Color all the vertices inSwith the colorc.

Delete all the vertices ofSfromG.

Return this coloring and the number of colors used.Here, the colors are numbered as 1,2,3,…. In this and the previous parts, do not destroy the original graph (while deleting vertices), because you are going to need it in the next part. You may alter a copy of

G. Alternatively, you can effect deletion by using special markers against vertices.Greedy edge coloring- In order to color the edges of
G= (V,E), you contruct theline graphL(G) = (V′,E′) ofGdefined as follows. The vertex setV′ ofL(G) is the same as the edge setEofG. Two vertices inL(G) (that is, two edges inE) are adjacent (inE′) if and only if the edges share a common endpoint. Evidently, an edge coloring ofGis the same as a vertex coloring ofL(G). Write a function that, upon the input ofG, returns the line graphL(G). Run the above greedy vertex-coloring algorithm on the returned graph. Report the coloring produced and the number of colors used. Notice that bothGandL(G) are undirected graphs and can be stored in the same format. They differ only by the formats of the vertex names. ForG, the vertices can be named as 0,1,2,…,n−1, whereas forL(G), the vertices are named by a pair of such integers.## Sample Output

n = 20 p = 0.1 +++ The graph before vertex coloring 0 [0] : 3 [0] 19 [0] 1 [0] : 12 [0] 2 [0] : 9 [0] 12 [0] 18 [0] 3 [0] : 0 [0] 9 [0] 11 [0] 16 [0] 19 [0] 4 [0] : 5 [0] 5 [0] : 4 [0] 12 [0] 13 [0] 6 [0] : 7 [0] : 11 [0] 15 [0] 8 [0] : 9 [0] : 2 [0] 3 [0] 10 [0] : 18 [0] 11 [0] : 3 [0] 7 [0] 16 [0] 12 [0] : 1 [0] 2 [0] 5 [0] 17 [0] 13 [0] : 5 [0] 16 [0] 14 [0] : 19 [0] 15 [0] : 7 [0] 19 [0] 16 [0] : 3 [0] 11 [0] 13 [0] 17 [0] : 12 [0] 19 [0] 18 [0] : 2 [0] 10 [0] 19 [0] : 0 [0] 3 [0] 14 [0] 15 [0] 17 [0] Vertex coloring done Number of colors used = 3 +++ The graph after vertex coloring 0 [1] : 3 [3] 19 [2] 1 [1] : 12 [3] 2 [1] : 9 [2] 12 [3] 18 [2] 3 [3] : 0 [1] 9 [2] 11 [1] 16 [2] 19 [2] 4 [1] : 5 [2] 5 [2] : 4 [1] 12 [3] 13 [1] 6 [1] : 7 [2] : 11 [1] 15 [1] 8 [1] : 9 [2] : 2 [1] 3 [3] 10 [1] : 18 [2] 11 [1] : 3 [3] 7 [2] 16 [2] 12 [3] : 1 [1] 2 [1] 5 [2] 17 [1] 13 [1] : 5 [2] 16 [2] 14 [1] : 19 [2] 15 [1] : 7 [2] 19 [2] 16 [2] : 3 [3] 11 [1] 13 [1] 17 [1] : 12 [3] 19 [2] 18 [2] : 2 [1] 10 [1] 19 [2] : 0 [1] 3 [3] 14 [1] 15 [1] 17 [1] +++ The line graph before coloring (0,3) [0] : (0,19) [0] (3,9) [0] (3,11) [0] (3,16) [0] (3,19) [0] (0,19) [0] : (0,3) [0] (3,19) [0] (14,19) [0] (15,19) [0] (17,19) [0] (1,12) [0] : (2,12) [0] (5,12) [0] (12,17) [0] (2,9) [0] : (2,12) [0] (2,18) [0] (3,9) [0] (2,12) [0] : (1,12) [0] (2,9) [0] (2,18) [0] (5,12) [0] (12,17) [0] (2,18) [0] : (2,9) [0] (2,12) [0] (10,18) [0] (3,9) [0] : (0,3) [0] (2,9) [0] (3,11) [0] (3,16) [0] (3,19) [0] (3,11) [0] : (0,3) [0] (3,9) [0] (3,16) [0] (3,19) [0] (7,11) [0] (11,16) [0] (3,16) [0] : (0,3) [0] (3,9) [0] (3,11) [0] (3,19) [0] (11,16) [0] (13,16) [0] (3,19) [0] : (0,3) [0] (0,19) [0] (3,9) [0] (3,11) [0] (3,16) [0] (14,19) [0] (15,19) [0] (17,19) [0] (4,5) [0] : (5,12) [0] (5,13) [0] (5,12) [0] : (1,12) [0] (2,12) [0] (4,5) [0] (5,13) [0] (12,17) [0] (5,13) [0] : (4,5) [0] (5,12) [0] (13,16) [0] (7,11) [0] : (3,11) [0] (7,15) [0] (11,16) [0] (7,15) [0] : (7,11) [0] (15,19) [0] (10,18) [0] : (2,18) [0] (11,16) [0] : (3,11) [0] (3,16) [0] (7,11) [0] (13,16) [0] (12,17) [0] : (1,12) [0] (2,12) [0] (5,12) [0] (17,19) [0] (13,16) [0] : (3,16) [0] (5,13) [0] (11,16) [0] (14,19) [0] : (0,19) [0] (3,19) [0] (15,19) [0] (17,19) [0] (15,19) [0] : (0,19) [0] (3,19) [0] (7,15) [0] (14,19) [0] (17,19) [0] (17,19) [0] : (0,19) [0] (3,19) [0] (12,17) [0] (14,19) [0] (15,19) [0] Edge coloring done Number of colors used = 5 +++ The graph after edge coloring (0,3) [2] : (0,19) [1] (3,9) [3] (3,11) [1] (3,16) [4] (3,19) [5] (0,19) [1] : (0,3) [2] (3,19) [5] (14,19) [2] (15,19) [3] (17,19) [4] (1,12) [1] : (2,12) [3] (5,12) [4] (12,17) [2] (2,9) [1] : (2,12) [3] (2,18) [2] (3,9) [3] (2,12) [3] : (1,12) [1] (2,9) [1] (2,18) [2] (5,12) [4] (12,17) [2] (2,18) [2] : (2,9) [1] (2,12) [3] (10,18) [1] (3,9) [3] : (0,3) [2] (2,9) [1] (3,11) [1] (3,16) [4] (3,19) [5] (3,11) [1] : (0,3) [2] (3,9) [3] (3,16) [4] (3,19) [5] (7,11) [2] (11,16) [3] (3,16) [4] : (0,3) [2] (3,9) [3] (3,11) [1] (3,19) [5] (11,16) [3] (13,16) [1] (3,19) [5] : (0,3) [2] (0,19) [1] (3,9) [3] (3,11) [1] (3,16) [4] (14,19) [2] (15,19) [3] (17,19) [4] (4,5) [1] : (5,12) [4] (5,13) [2] (5,12) [4] : (1,12) [1] (2,12) [3] (4,5) [1] (5,13) [2] (12,17) [2] (5,13) [2] : (4,5) [1] (5,12) [4] (13,16) [1] (7,11) [2] : (3,11) [1] (7,15) [1] (11,16) [3] (7,15) [1] : (7,11) [2] (15,19) [3] (10,18) [1] : (2,18) [2] (11,16) [3] : (3,11) [1] (3,16) [4] (7,11) [2] (13,16) [1] (12,17) [2] : (1,12) [1] (2,12) [3] (5,12) [4] (17,19) [4] (13,16) [1] : (3,16) [4] (5,13) [2] (11,16) [3] (14,19) [2] : (0,19) [1] (3,19) [5] (15,19) [3] (17,19) [4] (15,19) [3] : (0,19) [1] (3,19) [5] (7,15) [1] (14,19) [2] (17,19) [4] (17,19) [4] : (0,19) [1] (3,19) [5] (12,17) [2] (14,19) [2] (15,19) [3]

## Submission site | Miscellaneous information | Home