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 nvertices and medges, the approach solves the k-vertex cover problem in expected time O(4km+m4logn)using a simple RLS-style mutation. This bound can be improved to O(4km+m2nklogn)by using standard mutation constrained to the vertices of the graph. We also prove that a slight modification of the algorithm can be used to find k-coverable subgraphs of arbitrary graphs that are maximal under edge inclusion. We prove that a runtime budget of Ω(2km3log2n)suffices to generate a maximal k-coverable subgraph with high probability. Finally, we empirically show that these subgraphs often retain a number of structural properties of the source graph. This has direct implications for benchmarking, as it allows for the generation of graphs that maintain certain correlation properties while controlling for the optimal cover size.