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.
| Main Authors: | , , |
|---|---|
| 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!
|
| Summary: | 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. |
|---|