Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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):
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.
We can't say what the runtime of your "algorithm" is because it is not a complete algorithm - too many non-trivial things that can be done in different ways.
It can be done quite trivially in O (n log n + v), where n is the number of nodes and v is the number of vertices. Sort the nodes by weight in O (n log n). Then iterate through the nodes from heaviest to lightest: If a node is not marked as "removed" then add it to S and mark its neighbours as "removed". You will try to remove at most v nodes (actually the number of neighbours of the heaviest nodes that you find).
The number is actually less than n log n + v, because when you remove a node with many neighbours, the number of remaining candidate nodes gets a lot smaller as well.
The n log n can likely be made smaller: Start sorting with Quicksort, but only sort the parts of the array with larger values. Then you can start removing the heaviest nodes, and as you do that, nodes are removed from the array, so you don't have to sort everything.
