## 3 Greedy Heuristics  
Greedy algorithms are very common techniques for constructing solutions to combinatorial optimization problems from scratch, in a step-by-step manner. They are either used as standalone algorithms, or as subordinate algorithmic components of more sophisticated metaheuristics. Algorithm 1 shows the pseudo-code of a basic greedy algorithm for the MPIDS problem. It takes as input a simple, connected undirected graph \(G=(V,E)\) representing an instance of the MPIDS problem and provides as output a subset of vertices \(S\subset V\) corresponding to a positive influence dominating set. This algorithm builds a solution step by step, starting from an empty solution \(S=\emptyset\). At each construction step, it adds one feasible vertex \(v^{*}\in\overline{S}\) to \(S\) until a valid solution is obtained. \(\overline{S}=V\setminus S\) denotes the set of vertices of \(V\) not belonging to \(S\). Note that this set initially contains all the vertices of the graph. ```
0: a simple, connected undirected graph \(G=(V,E)\)
0: a positive influence dominating set \(S\)
1:\(S\leftarrow\emptyset\)
2:while (\(S\) is not a valid PIDS solution) do
3:\(v^{*}\leftarrow\)argmax\(\{\)greedy_function\((v)\mid v\in\overline{S}\}\)
4:\(S\leftarrow S\cup\{v^{*}\}\)
5:endwhile
6:return\(S\)
```  
**Algorithm 1** MPIDS_Greedy()  
At each construction step, the choice of the solution component to be added to the current partial solution is made deterministically based on a so-called _greedy function_ which plays an important role for the performance of the algorithm. It evaluates each solution component by measuring the local improvement obtained by adding the corresponding component to the incumbent partial solution. Most of the existing greedy algorithms for the MPIDS problem are based on at least one of the two greedy functions that are known as _cover-degree_ and _need-degree_. To define them, let \(S\subset V\) be the incumbent partial solution which is not yet a PIDS and \(h_{S}(v)=\lceil\frac{deg(v)}{2}\rceil-\lvert N_{S}(v)\rvert\) where \(N_{S}(v)=N(v)\cap S\) denotes the set of neighbors of \(v\in V\) belonging to \(S\). Then, we say that \(v\) is covered if \(h_{S}(v)\leq 0\) and not covered otherwise. Consequently, \(S\) is a valid solution (i.e., a PIDS) if and only if all vertices of \(V\) are covered. Now, for a given \(v\in\overline{S}\), _cover-degree_ and _need-degree_ are calculated as in Equation (7) and Equation (8), respectively. \[\textit{cover-degree}(v)=\lvert\{\,u\in N(v):h_{S}(u)>0\}\rvert \tag{7}\] \[\textit{need-degree}(v)=\sum_{u\in N(v)}\max(h_{S}(u),0) \tag{8}\]  
The first one represents the number of uncovered neighbors of \(v\) with respect to \(S\), whereas the second represents the total need of the uncovered neighbors of \(v\). Table 1 indicates which ones of these two greedy functions were used in the previous works from the literature. In the case in which an algorithm makes use of both functions, one of them was used as a secondary criterion for breaking ties in those cases in which the principal criterion provides the same value for several vertices. In the following, we recall the most recent and best-performing greedy algorithm, that is, [PERSON]'s greedy [17]. Note that, even though [PERSON]'s greedy uses the same greedy function (_cover-degree_) as [PERSON]'s greedy, its time complexity is much lower. This is for the following reason. While [PERSON]'s algorithm considers at each construction step any so-far unselected vertex for inclusion into the current partial solution, [PERSON]'s algorithm--after choosing the next unselected vertex \(v\) in ascending order with respect to the degree--only considers so-far unselected neighbors of \(v\) in subsequent construction steps until \(v\) is covered. The detailed pseudo-code for [PERSON]'s algorithm is provided in Algorithm 2. This pseudo-code is the same as in the original publication, but with using our notation and after removing some unnecessary details in order to improve the readability of the algorithm.