The minimum vertex cover problem is an ideal target for evolutionary algorithms because it is NP-complete [1]},
and appears in a broad range of practical applications.
Already in 1994 Bäck and Khuri [2]} defined the canonical
fitness function for EAs on vertex cover and provided experimental evidence that on some graph instances EAs can produce better approximate solutions than bespoke solvers.
In the years that followed runtime analysis of EAs tended to be heuristic and experimental, but recently rigorous theoretical analyses
have gained prominence.
The various approaches to this include proving runtime bounds for approximate solutions [3]}, [4]}, analyzing performance on best- or worst-case graph instances [5]}, [6]},
and implementing genetic mechanisms like crossover [7]}. It is also common for new research to define variations of well-studied EAs, like Olivieto et al.'s (1+1) EA with an additional `diversity maintenance mechanism' [6]}, or a fitness function with multiple objectives [9]}, [10]}.
