3
$\begingroup$

In most resources I could find, greedy algorithm is described as follows: for every vertex $v$, assign the minimal color not used by its neighbors.

The above could be implemented as:

colors[] <- 0 #assuming that 0 = not colored
for v in V:
  used[] <- false
  for u in N(v):
    if colors[u] != 0:
      used[colors[u]] <- true
  k <- 0
  while used[k] != 0:
    k <- k + 1
  colors[v] <- k + 1 
return colors

It is a similar algorithm to the one presented here: https://cstheory.stackexchange.com/a/11147/69014, where the author states that its time complexity is $O(n + m)$. I don't understand how is that possible as the outermost loop iterates $n$ times and the inner while loop might take up to $\Delta$ iterations before finding the first unused color, hence resulting in $O(n\Delta)$ time complexity.

How could you achieve linear time complexity?

$\endgroup$
5
  • 1
    $\begingroup$ When considering a vertex of degree $d$, there are at most $d$ colors used by its neighbours. This means that the inner while loop will run at most $d$ times before reaching an unused value. It also means that you can take the array "used" to be of length $d+1$ (simply ignore colors greater than that in the inner for loop). $\endgroup$
    – Tassle
    Apr 16, 2023 at 8:23
  • $\begingroup$ @Tassle doesn't it imply that the total time complexity is $O(n\Delta)$ just as I stated in the question? Reducing used array only affects the space used. $\endgroup$ Apr 16, 2023 at 9:04
  • 3
    $\begingroup$ Oh, I guess I see it. Two inner for loops is essentially edge traversal (each edge twice to be precise). Since inner while takes as much iterations as inner for, it does not affect the resulting time complexity of $O(m)$. We also need to zero-initialize colors array beforehand, hence $O(n + m)$. Is that correct? Was it linear all along? $\endgroup$ Apr 16, 2023 at 9:17
  • 4
    $\begingroup$ Yes, that was where I was going. It was already linear (as long as you are carefull to only initialize an array of length $O(d)$ for "used") $\endgroup$
    – Tassle
    Apr 16, 2023 at 15:57
  • 2
    $\begingroup$ Sure thing, thanks for pointing me in the right direction. Write an answer if you want and I’ll accept it. $\endgroup$ Apr 16, 2023 at 16:03

1 Answer 1

0
$\begingroup$

Short version

Use sets instead of lists for keeping track of colors

Long version

It is known that a greedy coloring will use at most $\Delta+1$ colors where $\Delta$ is the maximum degree of any node. Initialize each node with the same set of $\Delta+1$ colors.

When you color a node $u$, remove its color from the color set of each of its neighbors (and you can remove $u$ from the graph). Now choosing a color for each new uncolored node takes constant time, since you ca pop any color from its color set which includes all the colors that have not been removed due to one of its previously colored neighbors.

For each neighbor, removing the color of $u$ from its color set takes $O(1)$ (assuming no collisions in the hash table implementing the set).

Hence, for each node $u$, it takes $O(1)$ to color it and $O(\Delta)$ to update all of its neighbors' color sets once $u$ is colored. This gives the runtime $O(n\Delta)$.

Notice that each edge is used exactly twice when coloring nodes, and both operations using the edge are $O(1)$ (either removing a color from the neighbor's set, or skipping the neighbor because it is already colored). Therefore, we also get a runtime of $O(n+m)$.

$\endgroup$
2
  • 5
    $\begingroup$ Initializing a set of size $\Delta+1$ for each vertex already takes time $\Theta(n\Delta)$. $\endgroup$
    – Tassle
    Apr 16, 2023 at 7:56
  • $\begingroup$ Greedy colouring is meant to choose the smallest colour available for each node. Getting the smallest colour remaining in a set is not an $O(1)$ operation. It is $O(\Delta)$ if order is not maintained. Or, it could be $O(1)$ if you use $O(\log{\Delta})$-cost update operations to maintain ordered sets or a min-heap. $\endgroup$
    – JimN
    Jan 26 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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