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: Anais do X Encontro de Teoria da Computação, 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.