Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

Simple item page
dc.contributor.authorKearney, J.
dc.contributor.authorNeumann, F.
dc.contributor.authorSutton, A.M.
dc.contributor.conferenceConference on Foundations of Genetic Algorithms (FOGA) (30 Aug 2023 - 1 Sep 2023 : Germany)
dc.date.issued2023
dc.description.abstractWe 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.
dc.description.statementofresponsibilityJack Kearney, Frank Neumann, Andrew M. Sutton
dc.identifier.citationProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA, 2023), 2023, vol.abs/2409.10144, pp.96-104
dc.identifier.doi10.1145/3594805.3607134
dc.identifier.isbn9798400702020
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttps://hdl.handle.net/2440/143280
dc.language.isoen
dc.publisherACM
dc.publisher.placeOnline
dc.rights© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM
dc.source.urihttps://doi.org/10.1145/3594805.3607134
dc.subjectruntime analysis; parameterized complexity; vertex cover
dc.titleFixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Research Outputs