A Lagrangian Relaxation for the Generalized Target Set Selection Problem

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.