Harnessing Genetic Algorithm for Vertex Cover Problem

Abstract: The problem of finding a minimum vertex cover is an NP hard optimization problem. Some approximation algorithms for the problem have been proposed but most of them are neither optimal nor complete. The work proposes the use of the theory of natural selection via Genetic Algorithms (GAs) for solving the problem. The proposed work has been tested for some constrained inputs and the results were encouraging. The paper also discusses the application of genetic algorithms to the solution and the requisite analysis. The approach presents a Genetic Algorithms based solution to a problem