Complexity of this greedy algorithm to find the maximum independent set of a graph

Question

What is the complexity for this method which finds the maximum independent set of a graph?

I think it's O(|E|), is that right?

Greedy(G):
S = {}
While G is not empty:    Let v be a node with minimum degree in G
    S = union(S, {v})
    remove v and its neighbors from G
return S

Answer 1

For starters, note that this doesn't necessarily find a maximum independent set, though it always finds a maximal independent set.

As for the time complexity - this depends on how you represent the graph and how you implement each step. Here's one way to implement this algorithm in time O(m + n).

Suppose that you have the graph represented as an adjacency list. Create an array of booleans, one per node, that tracks whether the node can be added to the independent set. Initially, all of these booleans are true. Next, create an array of n buckets, initially empty. Then, iterate across the adjacency list. For each node, count up how many edges its adjacent to (its degree), then put that node into the bucket at that index. This setup takes time O(m + n) because each edge is scanned exactly once and we only need O(n) time to initialize the auxiliary structures.

Now, working from left to right, scan across the buckets. For each node in the bucket, do the following. If that node's auxiliary Boolean is marked false, skip the node. Otherwise, add the node to the set, mark its Boolean false, then iterate across the adjacency list entry for the node and mark all adjacent nodes' booleans false. This simulates deleting the node and its adjacent nodes from the graph.

Overall, this second step takes time O(m + n). To see this, note that it takes time O(n) to iterate across the buckets array, and across all iterations we visit every node and every edge exactly once. Therefore, this can be implemented in overall time O(m + n).

As you can see, though, it's tough to get this time bound. I'm not sure what your initial intuition was behind why this would take linear time, but I'd be careful to make sure that you didn't just directly jump from the pseudocode to linear time without thinking it through.

Hope this helps!