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

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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
    Volume425
    Pages (from-to)117-125
    ISSN0304-3975
    DOIs
    Publication statusPublished - 2012

    Bibliographical note

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

    Keywords

    • Randomized search heuristics
    • Iterated local search
    • Vertex cover
    • Random graphs
    • Karp–Sipser algorithm
    • e-phenonemon

    Cite this