Analysis of an iterated local search algorithm for vertex cover in sparse random graphs

Publication: Research - peer-reviewJournal article – Annual report year: 2012

View graph of relations

Recently, various randomized search heuristics have been studied for the solution of the minimum vertex cover problem, in particular for sparse random instances according to the G(n,c/n) model, where c>0 is a constant. Methods from statistical physics suggest that the problem is easy if c<e. This work starts with a rigorous explanation for this claim based on the refined analysis of the Karp–Sipser algorithm by Aronson et al. (1998) [1]. Subsequently, theoretical supplements are given to experimental studies of search heuristics on random graphs. For c<1, an iterated local search heuristic finds an optimal cover in polynomial time with a probability arbitrarily close to 1. This behavior relies on the absence of a giant component. As an additional insight into the randomized search, it is shown that the heuristic fails badly also on graphs consisting of a single tree component of maximum degree 3.
Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)117-125
StatePublished - 2012

Bibliographical note

This article is published in: "Special Issue on Theoretical Foundations of Evolutionary Computation" in the journal: "Theoretical Computer Science"

CitationsWeb of Science® Times Cited: 5


  • Randomized search heuristics, Iterated local search, Vertex cover, Random graphs, Karp–Sipser algorithm, e-phenonemon
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 7661693