Uma heurística construtiva gulosa eficiente para o problema do conjunto dominante independente mínimo

Abstract

The Minimum Independent Dominating Set (MIDS) problem is an optimization problem in graph theory whose objective is to find the smallest subset of vertices of a graph that is both independent and dominating. Being a NP-hard problem, there is no polynomial-time algorithm that can find an optimal solution for it, unless P = NP. To address problem instances where exact algorithms are intractable, some heuristic and metaheuristic approaches were proposed for this problem in the literature, aiming to find a good solution in tractable time. These approaches mainly focus on the local search phase, trying to improve a given initial solution. However, little effort has been spent on the construction phase, i.e., to try to build an already good initial solution. To fill this gap, in this work, we propose an efficient greedy constructive heuristic for the MIDS problem, with the objective of finding good-quality initial solutions without applying an intensification procedure. To evaluate the performance of our approach, we did a comparative study with the state-of-the-art heuristic approach for the MIDS problem, called MAE-PB. We show that, in average, our greedy method can find better solution quality in less time than MAE-PB, in addition to having little variability in solution quality and having no parameters to tune.