2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – HBeel Jan 13 '15 at 9:13
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Manuel Lafond Jan 13 '15 at 19:26
  • 1
    $\begingroup$ @Henry : actually, OP's algorithm finds a maximal independent set which is quite easier than finding a maximum one. $\endgroup$ – Manuel Lafond Jan 13 '15 at 19:28
  • 1
    $\begingroup$ What's the difference between a maximal and a maximum independent set? $\endgroup$ – HBeel Jan 13 '15 at 19:32
  • 1
    $\begingroup$ Apologies. I wasn't familiar with maximal set and read it as maximum $\endgroup$ – HBeel Jan 13 '15 at 19:36
3
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.