Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers
Date
2023
Authors
Kearney, J.
Neumann, F.
Sutton, A.M.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA, 2023), 2023, vol.abs/2409.10144, pp.96-104
Statement of Responsibility
Jack Kearney, Frank Neumann, Andrew M. Sutton
Conference Name
Conference on Foundations of Genetic Algorithms (FOGA) (30 Aug 2023 - 1 Sep 2023 : Germany)
Abstract
We 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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM