NP-hardness and evolutionary algorithm over new formulation for a Target Set Selection problem
Santiago V. Ravelo, Cláudio N. Meneses, Eduardo A.J. Anacleto · 2020
This work considers the Target Set Selection problem, which can be used to model the propagation and consumption of information, data, ideas and products through networks, with applications in marketing, medicine, sociology and bioinformatics. We propose a new version of the problem and prove it belongs to the NP-hard class. We also design an evolutionary algorithm that uses, in the crossover and mutation operators, exact solutions of sub-problems which were modeled by a new mathematical formulation. We test our approach over a benchmark of instances constructed from real-world data sets.