A Lagrangian Relaxation for the Generalized Target Set Selection Problem - Pereira, Felipe de C.; Rezende, Pedro J. de; Yunes, Tallys (Anais do Encontro de Teoria da Computação (ETC), 2025)
The Generalized Target Set Selection Problem (GTSSP) models the spread of information in social networks and is known to be NP-hard. We propose an integer programming formulation for the GTSSP, together with a promising Lagrangian relaxation approach. By relaxing a subset of constraints, we obtain a decomposable structure in which the relaxed problem can be split into a series of independent subproblems. Each subproblem corresponds to an instance of the Minimization Knapsack Problem, a weakly NP-hard problem solvable in pseudopolynomial time using a dynamic programming algorithm. We describe the decomposition scheme and discuss its computational complexity, highlighting its potential for use within an exact algorithm.