# Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining graph and color those 2, and so on. Compare this algorithm with the greedy algorithm: which is better?

I've given it some thought but I still can't get started with this problem, can you sketch a solution? It's a homework question

• There is no known polynomial time algorithm for finding a maximum independent set, it is np-complete. So even if this colours a graph better, it will be significantly slower than greedy colouring. Greedy colouring can perform arbitrarily bad, in particular there exists a vertex ordering that uses n colours on a crown graph with n nodes, when 2 are sufficient. Your algorithm is actually greedy colouring, that uses an (expensive) preprocessing step to find an optimal ordering – HBeel Jan 13 '15 at 9:13
• What does "better" mean here ? If it's in terms of time, Henry just gave you the answer. If it's rather in terms of the number of colors to use, then I don't know - but again, what does 'better' mean ? – Manuel Lafond Jan 13 '15 at 19:26
• @Henry : actually, OP's algorithm finds a maximal independent set which is quite easier than finding a maximum one. – Manuel Lafond Jan 13 '15 at 19:28
• What's the difference between a maximal and a maximum independent set? – HBeel Jan 13 '15 at 19:32
• Apologies. I wasn't familiar with maximal set and read it as maximum – HBeel Jan 13 '15 at 19:36

## 1 Answer

To compare the algorithms you need to specify how you are obtaining the independent set. For the sake of completeness, these are the algorithms:

GREEDY : Take an ordering of vertices $v_1,v_2,....v_n$. Color each vi with smallest integer not used to color its neighbours from $v_1$ to $v_i-1$

INDEPENDENT SET : Take an ordering of vertices $S = [v_1,v_2,.....v_n]$. To create independent set, pick $v_1$ and add it to $I =${}. From $S$, repetitively pick $v_i$ with smallest index not adjacent to any vertex in $S$. Give them a color and remove them from $S$. Repeat until $S$ is empty.

To compare the algorithms, let us take same ordering of vertices.

Consider all the vertices you assign color $1$ by greedy algorithm. By using independent set algorithm, in iteration $1$, we get $I$ as the set of vertices assigned 1 as they don't have edges between them and any other vertex has at least one of the color $1$ vertices as their neighbours (as otherwise they would've been given color $1$). Similarly, in the $i$th iteration of Independent set algorithm, we get vertices colored $i$.

Hence, both the algorithms give the same output for a given ordering.

P.S. "better" here refers to no. of colors as the chapter the question is derived from doesn't deal with time and space complexities.