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 \(O{\left( 4^k m + m^4 \log n \right) }\) using a simple RLS-style mutation. This bound can be improved to \(O{\left( 4^k m + m^2 n k \log n\right) }\) by using standard mutation constrained to the vertices of the graph.