Minimum Positive Influence Dominating Set (MPIDS)

Problem Description

This project focuses on the Minimum Positive Influence Dominating Set (MPIDS) problem. Given an undirected graph $G = (V, E)$, a Positive Influence Dominating Set (PIDS) is defined as a vertex subset $D \subseteq V$ where, for any vertex $v \in V$, at least half of its neighbors are members of $D$. Formally, this condition is expressed as $ |D \cap N(v)| \geq |N(v)|/2 \ \forall v \in V$. The objective of the MPIDS problem is to ascertain a PIDS with the minimum possible cardinality. Lin et al. [1] formally defined this problem, and Wang et al. [2] demonstrated it to be an $\mathcal{NP}$-hard problem for general graphs. In this framework, a social network is formally modeled as an undirected graph $G=(V, E)$, with $V$ representing users and $E$ representing connections. An edge $(u,v) \in E$ indicates a relationship and potential for influence between users $u$ and $v$. $N(v)$ denotes the set of vertices adjacent to $v$, i.e., ${u \in V : (u,v) \in E}$.

Industrial Context

The principles of social influence, and by extension the MPIDS problem, have significant industrial implications beyond academic research. In viral marketing, understanding and leveraging social influence allows companies to identify key individuals who can efficiently disseminate product information or promote adoption, leading to more cost-effective campaigns. In public health, identifying minimal dominating sets can aid in strategically targeting interventions (e.g., vaccination campaigns or health awareness messages) to control disease outbreaks effectively. For e-learning platforms, identifying influential users can enhance recommendation systems, suggesting relevant content or peers for collaborative learning. Furthermore, these concepts are vital in fields like counter-terrorism or crime prevention, where understanding influence propagation can help disrupt malicious networks by targeting key individuals.

Common Challenges

A significant limitation in solving MPIDS problems arises from the substantial scale of contemporary social networks. The sheer size of these networks often renders direct application of mathematical models computationally intractable, occasionally precluding the identification of even a feasible solution within reasonable timeframes. For instance, the linear integer programming model for MPIDS, as defined by Lin et al. [1], becomes infeasible for large graphs due to the massive number of binary variables assigned to each vertex. This computational barrier necessitates the development of more scalable solution approaches, as exact methods cannot provide timely or even any solutions for real-world social network instances.

Solution Approaches

Given the computational challenges, the existing literature proposes various greedy, heuristic, and metaheuristic methodologies to address the MPIDS problem.

Greedy and Heuristic Approaches

Wang et al. [2] pioneered a greedy algorithm that iteratively selects the vertex with the broadest influence. Raei et al. [5] improved upon this by introducing the cover-degree parameter to prioritize vertices. Pan [4] further advanced greedy strategies with the Fast Greedy Algorithm (FGA), which optimizes influence propagation through neighborhood exploration and prioritized dominance. The Improved Greedy Algorithm (IGA-PIDS) by Bouamama et al. [3], building on FGA, incorporates need-degree and cover-degree for enhanced prioritization, alongside initial network pruning and a final sieving process.

Metaheuristic Approaches

The field also benefits from diverse metaheuristic algorithms. Lin et al. [1] presented the ILPMA memetic algorithm, which combines the mathematical formulation with a Tabu Search for local optimizations. Akbay and Blum [6] proposed the Construct, Merge, Solve and Adapt (CMSA) algorithm, generating and merging solutions through adaptive structures. A self-adaptive variant refined this by dynamically adjusting the number of generated solutions per iteration [7]. The Iterated Carousel Greedy (ICG) algorithm [8] replaced Tabu Search with an iterative destruction and reconstruction of the dominating set.

Most recently, the FastPIDS algorithm by Sun et al. [9] has emerged as a state-of-the-art solution. It introduces several reduction rules for dominance set generation and reuses the need-degree function. FastPIDS integrates a greedy construction using a hybrid criterion with a local search based on vertex swapping, complemented by a two-level satisfaction judgment (TLSJ) mechanism. This TLSJ mechanism leverages two propositions to discern promising partial dominance sets, guiding the addition of new vertices via the hybrid heuristic. FastPIDS is currently the best-performing algorithm according to the literature.

Proposals

A novel proposal introduced in this work for solution improvement is the Piercing Local Search (PLS). This method is designed to strategically eliminate vertices from a localized region of the current solution, creating a “hole”, and then intelligently reconstruct the solution to potentially find a smaller, yet still feasible, dominating set.

The PLS operates iteratively: it systematically considers each vertex in the current dominating set D as a potential “center” for a Pierce operation. This Pierce operation recursively removes the central vertex and a set of its neighbors up to a specified depth $\delta$, deliberately creating a “hole” in the solution. Following this destruction phase, the incomplete solution is Reconstructed using a greedy criterion, ensuring feasibility. Finally, a RemoveRedundant procedure is applied to further optimize the solution by eliminating superfluous vertices while manteining feasibility. If an improved solution (i.e., one with a smaller cardinality) is found, the process restarts, otherwise it continues until no further improvements are observed or a maximum runtime is reached.

Apart from this novel local search procedure, several metaheuristics have been studied for this problem.

Greedy Randomized Adaptive Search Procedure (GRASP)

This multi-start metaheuristic involves an iterative process of constructing a greedy randomized solution and subsequently improving it via a local search. The construction phase often includes a “restricted candidate list” (RCL) from which elements are randomly selected, introducing a form of “piercing” or selective disruption of greedy choices to explore diverse solutions. [10]

Basic Variable Neighborhood Search (BVNS)

As described, this metaheuristic systematically explores different neighborhood structures. Its shaking phase, which serves to perturb the current solution and escape local optima, involves a controlled “piercing” by removing a specified number of nodes (determined by parameter k) from the solution, creating holes that are then intelligently reconstructed.

Iterated Greedy (IG)

This algorithm operates through an iterative cycle of destruction and reconstruction. A portion of the current solution is “pierced” or destroyed by removing elements, followed by a constructive phase that rebuilds the solution. Optionally, a local search can be applied after reconstruction to further refine the perturbed solution.

References

[1] Lin, G., Guan, J., Feng, H.: An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks. Physica A: Statistical Mechanics and its Applications 500, 199–209 (Jun 2018). https://doi.org/10.1016/j.physa.2018.02.119 [2] Wang, F., Du, H., Camacho, E., Xu, K., Lee, W., Shi, Y., Shan, S.: On positive influence dominating sets in social networks. Theoretical Computer Science 412(3), 265–269 (Jan 2011). https://doi.org/10.1016/j.tcs.2009.10.001 [3] Bouamama, S., Blum, C.: An improved greedy heuristic for the minimum positive influence dominating set problem in social networks. Algorithms 14(3), 79 (Feb 2021). https://doi.org/10.3390/a14030079 [4] Pan, J., Bu, T.M.: A fast greedy algorithm for finding minimum positive influence dominating sets in social networks. In: IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). p. 360–364. IEEE (Apr 2019). https://doi.org/10.1109/infcomw.2019.8845129 [5] Raei, H., Yazdani, N., Asadpour, M.: A new algorithm for positive influence dominating set in social networks. In: 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. p. 253–257. IEEE (Aug 2012). https://doi.org/10.1109/asonam.2012.51 [6] Akbay, M.A., Blum, C.: Application of cmsa to the minimum positive influence dominating set problem. In: Artificial Intelligence Research and Development, pp. 17–26. IOS Press (Oct 2021). https://doi.org/10.3233/faia210112 [7] Akbay, M.A., López Serrano, A., Blum, C.: A self-adaptive variant of CMSA: Application to the minimum positive influence dominating set problem. International Journal of Computational Intelligence Systems 15(1) (Jul 2022). https://doi.org/10.1007/s44196-022-00098-1 [8] Shan, Y., Kang, Q., Xiao, R., Chen, Y., Kang, Y.: An iterated carousel greedy algorithm for finding minimum positive influence dominating sets in social networks. IEEE Transactions on Computational Social Systems 9(3), 830–838 (Jun 2022). https://doi.org/10.1109/tcss.2021.3096247 [9] Sun, R., Wu, J., Jin, C., Wang, Y., Zhou, W., Yin, M.: An efficient local search algorithm for minimum positive influence dominating set problem. Computers & Operations Research 154, 106197 (Jun 2023). https://doi.org/10.1016/j.cor.2023.106197 [10] Penedo, I., Lozano-Osorio, I., Sánchez-Oro, J., Cordón, O.: Resolución del problema de conjunto dominante de influencia positiva mínima en redes sociales mediante metaheurísticas. XVI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (2025). https://openreview.net/forum?id=oKfvNtHU7c

Acknowledgments

The authors appreciate the support of the Comunidad Autónoma de Madrid (grant ref. TEC-2024/COM-404), Ministerio de Economía y Competitividad (grant ref. PID2021-125709OA-C22), and Ministerio para la Transformación Digital y de la Función Pública (Cátedra ENIA AI4DDS, grant ref. TSI-100930-2023-3).