Heuristic Approach for Solving the Dual Dominating Set Problem With Conflicts

Abstract

This paper introduces a novel combinatorial optimization problem, the Dual Dominating Set Problem with Conflicts (DDSP-C), which extends the classical Dominating Set Problem by requiring the identification of two disjoint dominating sets under pairwise conflict constraints. Such constraints prohibit specific node pairs from appearing in different dominating sets, reflecting practical considerations in facility location and resource allocation. We present an Integer Linear Programming (ILP) formulation to model the problem precisely and propose a metaheuristic solution approach based on the Greedy Randomized Adaptive Search Procedure (GRASP). The GRASP algorithm combines a randomized greedy construction with a local search phase, aiming to efficiently generate high-quality solutions. Experiments on random instances show the approach’s effectiveness and reveal insights into problem complexity across different graph densities and conflict levels.