Greedy Local Search and Vertex Cover in Sparse Random Graphs

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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. Subsequently, theoretical supplements are given to experimental studies of search heuristics on random graphs. For c <1, a greedy and randomized 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
    Title of host publicationTheory and Applications of Models of Computation : 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings
    PublisherSpringer
    Publication date2009
    Pages410-419
    ISBN (Print)978-3-642-02016-2
    DOIs
    Publication statusPublished - 2009
    Event6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009) - Changsha, China
    Duration: 18 May 200922 May 2009

    Conference

    Conference6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009)
    CountryChina
    CityChangsha
    Period18/05/200922/05/2009
    SeriesLecture Notes in Computer Science
    Volume5532
    ISSN0302-9743

    Bibliographical note

    Extended abstract.

    Fingerprint Dive into the research topics of 'Greedy Local Search and Vertex Cover in Sparse Random Graphs'. Together they form a unique fingerprint.

    Cite this