## 4 The Proposed Algorithm
### The Greedy Procedure  
The pseudo-code of IGA-PIDS is given in Algorithm 3. It receives as input a problem instance that consists of a simple, connected undirected graph \(G=(V,E)\) with \(n\) vertices, and works as follows. First, the given graph is pruned by applying procedure GraphPruning(G) (see Algorithm 4) which returns a partial solution \(S\). This procedure identifies vertices that must form part of the optimal solution and adds them to \(S\). This is done in order to speed up the process of solution construction of the greedy algorithm. Suppose that \(v\in V\) is a pendant vertex, i.e., \(deg(v)=1\), and let \(u\) be its unique neighbor. First, \(u\) is then added to \(S\), because \(v\) must be covered and can only be covered by \(u\). Second, if the degree of \(u\) is two--that is, \(deg(u)=2\), let \(w\
eq v\) be the second neighbor of \(u\). As \(u\) must covered by exactly one vertex, and as no other vertex benefits from choosing \(v\) for covering \(u\), we can savely choose \(w\) for covering \(u\). Therefore, \(w\) is added to \(S\).  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Algorithm Name** & **Algorithm Type** & **Greedy Function** & **Complexity** & **Year** & **Ref** \\ \hline [PERSON]’s algorithm & Greedy & _cover-degree_ & \(O(n^{3})\) & 2011 & [13] \\ [PERSON]’s algorithm & Greedy & _need-degree_ & \(O(n^{2})\) & 2012 & [15] \\ [PERSON]’s algorithm & Greedy & both & - & 2016 & [16] \\ [PERSON]’s algorithm & Greedy & _cover-degree_ & \(O(nlgn+m)\) & 2019 & [17] \\ ILPMA & A hybrid metaheuristic & _cover-degree_ & - & 2018 & [20] \\ HSIA & A hybrid metaheuristic & _cover-degree_ & - & 2019 & [22] \\ (GA + PSO) & \multicolumn{1}{c}{} & & & \\ \hline \hline \end{tabular}
\end{table}
Table 1: Greedy functions used in the existing literature.  
At this point, let \(C\) be the set of all so-far uncovered vertices. Next, the algorithm picks yet uncovered vertices from \(C\) in (increasing) order of their degrees. The chosen vertex \(v_{i}\) is then covered by choosing neighbors of \(v_{i}\) from \(N_{\overline{S}}(v_{i})\) until \(v_{i}\) is covered. In particular, at each step the vertex with the largest _cover-degree_ value of all vertices in \(N_{\overline{S}}(v_{i})\) is chosen. If tie breaking is necessary, it is done with the _need-degree_ function (see lines 8 and 9 of Algorithm 3). Finally, the algorithm is terminated when all vertices are covered, that is, when \(S\) corresponds to a valid PIDS solution.  
```
0: a simple, connected undirected graph \(G=(V,E)\)
0: a positive influence dominating set \(S\)
1:\(S\leftarrow\mathsf{GraphPruning}(G)\)
2:\(C\leftarrow\) set of all so-far uncovered vertices
3: Rename the vertices from \(C\) such that \(\{v_{1},v_{2},\cdots,v_{|C|}\}\) are the vertices in ascending order of the degree
4:\(\overline{S}\gets V\setminus S\)
5:while\(S\) is not a valid PIDS solution do
6: Let \(v_{i}\) be an un-covered vertex with the smallest sub-index in \(C\)
7:\(\rho\gets h_{S}(v_{i})\)
8:for\(j=1\)to\(\rho\)do
9:\(cd_{max}\leftarrow\max\{\textit{cover-degree}(u)\mid u\in N_{\overline{S}}(v_ {i})\}\)
10:\(u^{*}\leftarrow\operatorname*{argmax}\{\textit{need-degree}(u)\mid u\in N_{ \overline{S}}(v_{i})\wedge\textit{cover-degree}(u)=cd_{max}\}\)
11:\(S\gets S\cup\{u^{*}\}\)
12:\(\overline{S}\gets V\setminus\hat{S}\)
13:endfor
14:\(C\leftarrow\)\(\bigcup\{v_{i}\}\)
15:endwhile
16:\(\operatorname{Reduce}(S)\)
17:return\(S\)
```  
**Algorithm 3** IGA-PIDS: Improved greedy algorithm for the MPIDS problem