## 2 The Minimum Positive Influence Dominating Set Problem  
We describe the MPIDS problem by starting with basic notions and underlying definitions which are used throughout this paper. Let \(G=(V,E)\) be an undirected graph that is both simple and connected. (Note that an undirected graph is called _simple_ if it does not contain multiple edges between pairs of vertices and loops.) Hereby, \(V\) is a set of \(n\) vertices--representing, for example, people--and \(E\subset V\times V\) is a set of \(m\) edges modeling, for example, relationships between those people. Let \(v\) and \(u\) be two distinct vertices from \(G\). Now, \(v\) and \(u\) are said to be adjacent (neighbors) if they are connected by an edge. Further, the _open neighborhood_ of \(v\) is defined as \(N(v):=\{u\in V\mid(v,u)\in E\}\). \(N(v)\) is often simply called the neighborhood of \(v\) in \(G\). The _closed neighborhood_ of \(v\) is defined as \(N[v]:=N(v)\cup\{v\}\), i.e., \(N[v]\) includes all vertices adjacent to \(v\), including \(v\) itself. The degree of \(v\), denoted by \(deg(v)\), is the number of \(v\)'s neighbors, that is, \(deg(v)=|N(v)|\). A vertex of degree one--that is \(|N(v)|=1\)--is called a _pendant vertex_.  
**Definition 1** (Dominating set).: _A dominating set (DS) of \(G\) is a subset \(D\subseteq V\) such that each vertex \(v\in V\setminus D\) is adjacent to at least one vertex in \(D\)._  
**Definition 2** (Positive influence dominating set).: _A positive influence dominating set (PIDS) of \(G\) is a dominating set \(D\subseteq V\) such that each vertex \(v\in V\) has at least half of its open neighbors in \(D\), that is, at least \(\lceil deg(v)/2\rceil\) vertices of \(N(v)\) must belong to \(D\) for each \(v\in V\)._  
Figure 0(b) shows an example of a DS of the graph shown in Figure 0(a), where black vertices represent those that are in the DS. Figure 0(c) provides an example of a PIDS (black vertices). Vertex 6, for example, has degree 3 and \(\lceil 3/2\rceil=2\) of its neighbors (vertex 4 and vertex 2) are part of the PIDS.  
**Definition 3** (Minimum dominating set problem).: _Given an undirected simple graph \(G=(V,E)\), the minimum dominating set (MDS) problem asks to find a DS of \(G\) of minimum cardinality._  
This problem can be easily formulated in terms of an integer linear program (ILP). For convenience, we assume that \(V\) is enumerated as \(v_{1},v_{2},\ldots,v_{n}\). A binary variable \(x_{i}\in\{0,1\}\) is associated to each vertex \(v_{i}\in V\) such that \(x_{i}=1\) if and only if \(v_{i}\) is part of the optimal solution, and \(x_{i}=0\) otherwise. The ILP model can then be stated as follows.  
\[\textbf{Minimize} \sum_{i=1}^{n}x_{i} \tag{1}\] \[\textbf{Subject to} \sum_{v_{j}\in N[v_{i}]}x_{j}\geq 1\quad\forall v_{i}\in V\] (2) \[x_{i}\in\{0,1\} \tag{3}\]  
Equation (2) ensures that the generated solution is a dominating set. Remember that \(N[v_{i}]\) is the closed neighborhood of \(v_{i}\).  
**Definition 4** (Minimum positive influence dominating set problem).: _Given an undirected simple graph \(G=(V,E)\), the minimum positive influence dominating set (MPIDS) problem asks to find a PIDS of \(G\) of minimum cardinality._  
Based on the ILP model of the MDS problem from above, the MPIDS problem can also easily be stated in terms of an ILP as follow.  
\[\textbf{Minimize} \sum_{i=1}^{n}x_{i} \tag{4}\] \[\textbf{Subject to} \sum_{v_{j}\in N(v_{i})}x_{j}\geq\left\lceil\frac{deg(v_{i})}{2} \right\rceil\quad\forall v_{i}\in V\] (5) \[x_{i}\in\{0,1\} \tag{6}\]  
Figure 1: An illustrative example of the MPIDS problem. Black vertices form part of the solutions.  
Equation (5) ensures that a feasible solution contains at least half of the neighbors of each vertex \(v_{i}\in V\).