Applying Genetic Algorithms to Validate a Conjecture in Graph Theory: The Minimum Dominating Set Problem

Abstract: This paper presents a case study where the interdisciplinary approach between artificial intelligence, specifically genetic algorithms, and discrete mathematics has been instrumental in verifying a conjecture in graph theory. The focus of our research lies in the Minimum Dominating Set (MDS) problem, which involves identifying a dominating set with the minimum cardinality for a given graph. While previous works have primarily aimed at utilizing genetic algorithms to efficiently find satisfactory solutions to the MDS problem, our study aims to discover the optimal solution. The Rank GA algorithm employed in our work possesses the ability to escape local optima while simultaneously conducting local search to refine the best available solution. Since the MDS problem is known to be NP-hard, the characteristics of Rank GA, coupled with the identification of regularities in one of the solutions, enabled us to verify the conjecture for graphs comprising 30, 80, 312, and 800 vertices. This research serves as a testament to the versatility of genetic algorithms, showcasing their utility not only in practical problem-solving but also in tackling theoretical challenges.

Bibliographic Details

Main Authors:	Cervantes-Ojeda,Jorge, Gómez-Fuentes,María C., Fresán-Figueroa,Julián A.
Format:	Digital revista
Language:	English
Published:	Instituto Politécnico Nacional, Centro de Investigación en Computación 2023
Online Access:	http://www.scielo.org.mx/scielo.php?script=sci_arttext&pid=S1405-55462023000401089
Tags:	Add Tag No Tags, Be the first to tag this record!