Tackling the α-Domination Problem Heuristically

Abstract

We focus on the α-domination problem, which is capable of modeling influence phenomena in social networks. It formally asks for a minimum cardinality subset of vertices of a given graph such that any vertex is either included in this subset or at least a fraction α of its neighbors is (0<α≤1). We address the search for solutions of high quality within a tight margin of computation time by designing, firstly, a Greedy Randomized Adaptive Search Procedure and, secondly, a Configuration Checking metaheuristic. The latter excels in terms of solution quality and speed and is able to outperform an integer programming formulation solved by the commercial solver Gurobi on a majority of tested instances which have thousands of vertices.