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

Jack Kearney, Frank Neumann, Andrew M. Sutton

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 loga…