Kearney, J.Neumann, F.Sutton, A.M.2024-11-152024-11-152023Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA, 2023), 2023, vol.abs/2409.10144, pp.96-1049798400702020https://hdl.handle.net/2440/143280We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every 𝑂(𝑛 log𝑛) steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs 𝑝 > 0.71. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation. We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime.en© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACMruntime analysis; parameterized complexity; vertex coverConference paper10.1145/3594805.36071342024-08-26652859Neumann, F. [0000-0002-2721-3618]