A Lagrangian Relaxation for the Generalized Target Set Selection Problem

• Felipe de C. Pereira UFS
• Pedro J. de Rezende UNICAMP
• Tallys Yunes University of Miami

DOI: https://doi.org/10.5753/etc.2025.9069

Resumo

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.

Referências

Ackerman, E., Ben-Zwi, O., and Wolfovitz, G. (2010). Combinatorial Model and Bounds for Target Set Selection. Theoretical Computer Science, 411(44):4017–4022.

Chen, N. (2009). On the Approximability of Influence in Social Networks. SIAM Journal on Discrete Mathematics, 23(3):1400–1415.

Chen, W., Lakshmanan, L., and Castillo, C. (2013). Information and Influence Propagation in Social Networks. Synthesis Lectures on Data Management, 5(4):1–177.

Fisher, M. L. (1981). The lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1–18.

Kellerer, H., Pferschy, U., and Pisinger, D. (2004). Knapsack Problems. Springer.

Li, Y., Fan, J., Wang, Y., and Tan, K. (2018). Influence Maximization on Social Graphs: A Survey. IEEE Transactions on Knowledge and Data Engineering, 30(10):1852–1872.

Pereira, F. C. and de Rezende, P. J. (2023). The Least Cost Directed Perfect Awareness Problem: Complexity, Algorithms and Computations. Online Social Networks and Media, 37-38:100255.

Pereira, F. C., de Rezende, P. J., and de Souza, C. C. (2021). Effective Heuristics for the Perfect Awareness Problem. In Proocedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, pages 489–498.

Pereira, F. C., de Rezende, P. J., and Yunes, T. (2024). Minimizing the Cost of Leveraging Influencers in Social Networks: IP and CP Approaches. In Proceedings of the 21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 111–127.

Raghavan, S. and Zhang, R. (2019). A Branch-and-Cut Approach for the Weighted Target Set Selection Problem on Social Networks. INFORMS Journal on Optimization, 1(4):304–322.

Ravelo, S. V. and Meneses, C. N. (2021). Generalizations, Formulations and Subgradient Based Heuristic with Dynamic Programming Procedure for Target Set Selection Problems. Computers & Operations Research, 135:105441.

Shakarian, P., Eyre, S., and Paulo, D. (2013). A Scalable Heuristic for Viral Marketing Under the Tipping Model. Social Network Analysis and Mining, 3(4):1225–1248.

Spencer, G. and Howarth, R. (2013). Maximizing the spread of stable influence: Leveraging norm-driven moral-motivation for green behavior change in networks. CoRR, abs/1309.6455.

Zhao, X., Luh, P. B., and Wang, J. (1999). Surrogate gradient algorithm for lagrangian relaxation. Journal of Optimization Theory and Applications, 100(3):699–712.