RAND-P_3: Selection of Minimum Vertex Sets for Total Graph Activation via Adaptive Reinforcement

We consider the problem of selecting a minimal subset of vertices in a graph whose initial activation is sufficient to activate the entire structure through a local dynamic. We model this process through P_3 convexity, in which a vertex is activated when it has at least two active neighbors. The associated problem, known as the P_3 envelope number, is NP-complete. To deal with this difficulty, we propose the RAND-P_3 algorithm, a randomized heuristic with adaptive reinforcement. The central idea is to progressively increase the probability of selecting vertices that appear in viable solutions, directing the search to promising regions of the solution space.  In addition, we introduce adversarial graph classes designed to exploit structural limitations of deterministic heuristics in the literature. We showed experimentally that, in these scenarios, deterministic methods tend to overestimate the size of the initial sets, while randomness with RAND-P_3 reinforcement presents greater robustness and better solution quality.