The rise of the internet and social networks has posed new challenges in studying people’s behavior on these platforms. People tend to trust or align with a small group of users, leading to the development of viral marketing techniques to effectively propagate information about products or services. This has led to the definition of problems related to social influence maximization/minimization and dominance sets. The Minimum Positive Influence Dominating Sets (MPIDS) problem involves finding a minimum cardinality dominance set to influence an entire social network. For a vertex to be influenced, at least half of its neighbors must be in the dominance set. Considering that MPIDS is an NP-hard problem, where exact approximations are impractical due to the size of social networks, this work proposes using Basic Variable Neighborhood Search (BVNS). Given an initial solution generated by a constructive method, this metaheuristic consists of two phases: a shaking and an improvement phase. In the shaking phase, the solution is modified by removing and reconstructing it using a randomized greedy approach. The improvement phase involves an innovative local search strategy based on generating holes, which removes the delta-neighborhood of a vertex to facilitate a greedy solution reconstruction.