# Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm

The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as possible.

My question is that I want to find the time complexity of the following algorithm (when applied on $N \times N$ grid graphs): • What have you tried so far? Does the reference question help? Jan 10, 2017 at 14:32
• @adrianN I've tried something similar but i get confused at the while loop because you have to delete not only the node but its neighbors also. Jan 10, 2017 at 14:44
• ok, then please edit your question a) to fully state the problem that the algorithm is supposed to solve (that PDF link will likely be DMCA'd soon), b) clarify what exactly you're asking Jan 10, 2017 at 15:03
• @adrianN thanks i just corrected my question hope that now it helps Jan 10, 2017 at 15:13
• @Fotis: So how many delete operations are there, if you have N nodes? Answer: Exactly N. Jan 10, 2017 at 16:01

Let's analyze the runtime. In each iteration of the loop we look for the maximum weight node. If you do this naively, you look at all nodes. By using a clever data structure you could speed this up. Adding the node to S takes constant time for all reasonable set data structures. Now we remove $v_i$ and its neighbors. This can be done in time proportional to the number of incident edges at $v_i$ and at its neighbors, for reasonable graph representations, e.g. an adjacency list.

In your comment you stated that you had problems analyzing the algorithm because you didn't know the number of iterations of the loop. You could conservatively assume that you remove only $v_i$ itself to get a runtime of $O(|V| \times$finding the max$)$, so $O(|V|^2)$. Since $G$ is a grid graph, each node has degree at most four. So even if you assume optimistically that you remove five nodes in each iteration you get the same asymptotic runtime.

The running time of adding a vertex to the independent set $S$ is $O(1)$ if you use an appropriate set data structure, such as a linked list, an array, or a dictionary. Also, deleting a vertex $v$ from $G$ (once you have identified the vertex) takes time proportional to the number of neighbours, which, in this case, is bounded above by a constant ($4$), so it also takes $O(1)$ time.

The running time of your greedy algorithm will, therefore, be dominated by the costs of the maximum-weight vertex computations. I can think of three ways to implement this operation:

• Naive approach - $O(|V|)$: identifying the maximum-weight vertex of a graph takes linear time in the number of vertices if you explore all of them.

• Priority queue - $O(log \: |V|)$ : since you are doing repeated maximum computations, it makes sense to use a priority queue, which allows you to extract the maximum element in logarithmic time.

• Sorted array - $O(1)$ : the maximum-weight vertex of a graph can be identified in constant time if you sort the vertices by weight beforehand.

The number of times that the algorithm computes the maximum-weight vertex is equal to the number of iterations, which is $O(|V|)$. Therefore, the naive approach takes $O(|V|^2)$ time and the priority queue based solution takes $O(|V| \: log \: |V|)$ time. In the sorting-based solution, each iteration takes $O(1)$ time; however, the overall running time is not $O(|V|)$, but, rather, $O(|V| \: log \: |V|)$ because the running time is dominated by the sorting operation.

• I don't think you can improve on the $n\log n$ asymptotically. The independent set has linear size in grid graphs. Jan 11, 2017 at 8:39