Evolutionary Algorithms and the Vertex Cover Problem

Pietro Oliveto, Jun He, Xin Yao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Citations (Scopus)


Experimental results have suggested that evolutionary algorithms may produce higher quality solutions for instances of vertex cover than a very well known approximation algorithm for this NP-complete problem. A theoretical analysis of the expected runtime of the (1+1)-EA on a well studied instance class confirms such a conjecture for the considered class. Furthermore, a class for which the (1+1)-EA takes exponential optimization time is examined. Nevertheless, given polynomial time, the evolutionary algorithm still produces a better solution than the approximation algorithm. Recently, the existence of an instance class has been proved for which the (1+1)-EA produces poor approximate solutions, given polynomial time. Here it is pointed out that, by using multiple runs, the (1+1)-EA finds the optimal cover of each instance of the considered graph class in polynomial time.
Original languageEnglish
Title of host publicationIEEE Congress on Evolutionary Computation, 2007. CEC 2007.
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages8
ISBN (Electronic)978-1-4244-1340-9
ISBN (Print)978-1-4244-1339-3
Publication statusPublished - 1 Sept 2007
EventIEEE Congress on Evolutionary Computation, 2007 (CEC 2007) - Singapore, Singapore
Duration: 25 Sept 200728 Sept 2007


ConferenceIEEE Congress on Evolutionary Computation, 2007 (CEC 2007)


Dive into the research topics of 'Evolutionary Algorithms and the Vertex Cover Problem'. Together they form a unique fingerprint.

Cite this