Greedy Local Search and Vertex Cover in Sparse Random Graphs

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2009

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. 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
StatePublished - 2009
Event6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009) - Changsha, China

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.

CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 58365298