Abstract
In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We consider two different measures for the problem. The first measure is a very natural multi-objective one for the use of evolutionary algorithms and takes into account the number of chosen vertices and the number of edges that remain uncovered. The second fitness function is based on a linear programming formulation and proves to give better results. We point out that both approaches lead to a kernelization for the Vertex Cover problem. Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e., the expected runtime is bounded by $O(f(OPT) \cdot n^c)$, where $c$ is a constant and $f$ a function that only depends on $OPT$. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem.
Introduction
Evolutionary algorithms (EAs) are frequently utilized as robust heuristics for NP-hard optimization problems, yet they often lack the rigorous performance guarantees favored in theoretical computer science. This research bridges the gap between heuristic search and formal complexity theory by analyzing EAs through the lens of Parameterized Complexity.
The authors focus on the Vertex Cover problem—identifying the smallest set of vertices that "touches" every edge in a graph. While Vertex Cover is NP-hard, it is known to be Fixed-Parameter Tractable (FPT), meaning there are algorithms with runtimes like $O(f(k) \cdot n^c)$, where $k$ is the solution size. This paper demonstrates that general-purpose EAs, when designed with appropriate multi-objective fitness functions, naturally behave like these sophisticated FPT algorithms.
Methodology
The study analyzes a multi-objective EA called Global SEMO (Simple Evolutionary Multi-Objective Optimizer). Rather than searching for a single optimal solution, Global SEMO maintains a population of non-dominated solutions, effectively exploring a Pareto front. The researchers evaluate two distinct multi-objective fitness functions:
- The Natural Measure ($f_1$): Minimizes the number of chosen vertices and the number of edges left uncovered.
- The LP-based Measure ($f_2$): Minimizes the number of chosen vertices and the cost of a fractional vertex cover for the remaining uncovered edges, utilizing a Linear Programming (LP) relaxation of the problem.
To improve search efficiency, the authors implement an alternative mutation operator. Instead of standard bit-flipping with $1/n$ probability, this operator flips vertices incident to uncovered edges with a probability of $1/2$. This modification mimics the "branching" behavior found in traditional combinatorial FPT algorithms.
Theoretical Insights: Evolutionary Kernelization
A central contribution of this work is the concept of Evolutionary Kernelization. In parameterized complexity, kernelization is a preprocessing step that reduces a large instance into a small "kernel" whose size depends only on the parameter $k$. The authors prove that the EA's process of minimizing uncovered edges effectively performs this kernelization dynamically during the search.
Furthermore, the LP-based guidance ($f_2$) provides a structural roadmap for the algorithm. Because optimal fractional vertex covers are "half-integral" (values are 0, 1/2, or 1), they provide a mathematical framework that the EA can exploit to find the integer solution more efficiently than simple edge counting.
Key Results
The paper establishes rigorous upper bounds on the expected optimization time (the number of fitness evaluations required to find the optimum):
- With LP-based fitness ($f_2$): The EA finds a 2-approximation in $O(n^2 \log n + OPT \cdot n^2)$ time and the exact minimum vertex cover in $O(n^2 \log n + OPT \cdot n^2 + n \cdot 4^{OPT})$ time.
- With natural fitness ($f_1$): The EA finds an optimal solution in $O(OPT \cdot n^4 + n \cdot 2^{OPT + OPT^2})$ time.
These runtimes are classified as FPT because the exponential component of the complexity depends solely on the size of the optimal solution ($OPT$), while the dependence on the total number of vertices ($n$) remains polynomial. This represents a significant theoretical improvement over standard EAs, which typically require $n^{\Theta(OPT)}$ time for such problems.
Limitations and Future Work
While this research proves that EAs can be FPT, the exponential constants (e.g., $4^{OPT}$) remain higher than those of highly specialized, hand-crafted Vertex Cover algorithms. Additionally, the $f_2$ approach introduces polynomial overhead by requiring an LP solver (or maximum flow calculation) for every fitness evaluation.
Future research may extend this "Fixed-Parameter EA" framework to other NP-hard problems restricted by parameters like treewidth or to problems such as Cluster Editing and 3-Hitting Set. This work establishes a foundation for designing EAs that are not just heuristics, but theoretically grounded solvers for structured hard problems.
Summary updated