Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem

Simple item page
dc.contributor.authorBaguley, S.
dc.contributor.authorFriedrich, T.
dc.contributor.authorNeumann, A.
dc.contributor.authorNeumann, F.
dc.contributor.authorPappik, M.
dc.contributor.authorZeif, Z.
dc.contributor.conferenceGenetic and Evolutionary Computation Conference (GECCO) (15 Jul 2023 - 15 Jul 2023 : Lisbon, Portugal)
dc.contributor.editorPaquete, L.
dc.date.issued2023
dc.description.abstractParameterized 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.
dc.description.statementofresponsibilitySamuel Baguley, Tobias Friedrich, Aneta Neumann, Frank Neumann, Marcus Pappik, Ziena Zeif
dc.identifier.citationProceedings of the Genetic and Evolutionary Computation Conference (GECCO '23), 2023 / Paquete, L. (ed./s), pp.1537-1545
dc.identifier.doi10.1145/3583131.3590501
dc.identifier.isbn9798400701191
dc.identifier.orcidNeumann, A. [0000-0002-0036-4782]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttps://hdl.handle.net/2440/139312
dc.language.isoen
dc.publisherAssociation for Computing Machinery
dc.publisher.placeNew York, NY
dc.relation.granthttp://purl.org/au-research/grants/arc/FT200100536
dc.rightsยฉ 2023 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution International 4.0 License.
dc.source.urihttps://dl.acm.org/doi/proceedings/10.1145/3583131
dc.subjectEvolutionary Algorithms; Parameterized Complexity; Runtime Analysis
dc.titleFixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem
dc.typeConference paper
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
hdl_139312.pdf
Size:
637.49 KB
Format:
Adobe Portable Document Format
Description:
Published version
Download

Collections

Computer Science publications