Evolving Populations of Solved Subgraphs with Crossover and Constraint Repair

We introduce a population-based approach to solving parameterized graph problems for which the goal is to identify a small set of vertices subject to a feasibility criterion. The idea is to evolve a population of individuals where each individual corresponds to an optimal solution to a subgraph of the original problem. The crossover operation then combines both solutions and subgraphs with the hope to generate an optimal solution for a slightly larger graph. In order to correctly combine solutions and subgraphs, we propose a new crossover operator called generalized allelic crossover which generalizes uniform crossover by associating a probability at each locus depending on the combined alleles of the parents. We prove for graphs with n vertices and m edges, the approach solves the k-vertex cover problem in expected time O4^km+m⁴logn using a simple RLS-style mutation. This bound can be improved to O4^km+m²nklogn by using standard mutation constrained to the vertices of the graph.