TY - GEN

T1 - Greedy Local Search and Vertex Cover in Sparse Random Graphs

AU - Witt, Carsten

N1 - Extended abstract.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-02017-9_43

DO - 10.1007/978-3-642-02017-9_43

M3 - Article in proceedings

SN - 978-3-642-02016-2

T3 - Lecture Notes in Computer Science

SP - 410

EP - 419

BT - Theory and Applications of Models of Computation

PB - Springer

T2 - 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009)

Y2 - 18 May 2009 through 22 May 2009

ER -