Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Fixed-parameter evolutionary algorithms and the vertex cover problem
Author: Kratsch, S.
Neumann, F.
Citation: Algorithmica, 2013; 65(4):754-771
Publisher: Springer-Verlag
Issue Date: 2013
ISSN: 0178-4617
Statement of
Stefan Kratsch, Frank Neumann
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)⋅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.
Keywords: Evolutionary algorithms; Fixed-parameter tractability; Vertex cover; Randomized algorithms
Rights: © The Author(s) 2012. This article is published with open access at
RMID: 0020125694
DOI: 10.1007/s00453-012-9660-4
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_82824.pdfRestricted Access581.09 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.