Evolving Populations of Solved Subgraphs with Crossover and Constraint Repair

Area of Science:

• Computer Science
• Graph Theory
• Algorithm Design

Background:

• Parameterized graph problems involve finding small vertex sets meeting specific criteria.
• Existing methods may struggle with scalability and efficiency for complex graph structures.

Purpose of the Study:

• To develop a novel population-based approach for solving parameterized graph problems.
• To introduce a generalized allelic crossover operator for combining subgraph solutions.
• To analyze the runtime complexity and practical applicability of the proposed method.

Main Methods:

• Population-based evolutionary algorithm evolving solutions on subgraphs.
• Introduction of a generalized allelic crossover operator generalizing uniform crossover.
• Analysis of expected runtime for k-vertex cover using RLS-style and constrained mutations.

Main Results:

• The algorithm solves the k-vertex cover problem in expected time O(4km+m4logn) with RLS-style mutation.
• Runtime improves to O(4km+m2nklogn) with constrained mutation.
• A modified algorithm finds maximal k-coverable subgraphs with high probability within Ω(2km3log2n) runtime.
• Empirical results show generated subgraphs retain structural properties of the source graph.

Conclusions:

• The proposed population-based approach offers an efficient method for parameterized graph problems.
• The generalized allelic crossover operator effectively combines solutions from subgraphs.
• The ability to generate structurally representative subgraphs has implications for graph benchmarking.