Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem
Files
(Published version)
Date
2023
Authors
Baguley, S.
Friedrich, T.
Neumann, A.
Neumann, F.
Pappik, M.
Zeif, Z.
Editors
Paquete, L.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '23), 2023 / Paquete, L. (ed./s), pp.1537-1545
Statement of Responsibility
Samuel Baguley, Tobias Friedrich, Aneta Neumann, Frank Neumann, Marcus Pappik, Ziena Zeif
Conference Name
Genetic and Evolutionary Computation Conference (GECCO) (15 Jul 2023 - 15 Jul 2023 : Lisbon, Portugal)
Abstract
Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multiobjective algorithms for the๐-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most๐ vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution ๐๐๐ and๐. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the๐-separator uses linear programming methods and requires a non-trivial post-process to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the๐-separator problem.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
ยฉ 2023 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution International 4.0 License.