Optimizing the Weight Stable Set Attack With Budget Constraint

This research paper presents algorithms for solving the weight stable set attack problem, which involves removing nodes from a social network while staying within a budget constraint to minimize the remaining network's influence potential. The authors develop a 2α-approximation algorithm (an algorithm guaranteed to find solutions within twice the optimal answer) for networks without odd cycles and extend it to general networks, comparing it against a genetic algorithm (a problem-solving technique inspired by natural evolution) through experiments on both artificial and real-world networks.