Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

Jack Kearney; Frank Neumann; Andrew M. Sutton

doi:10.1145/3594805.3607134

Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

Jack Kearney, Frank Neumann, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every O(n log n) steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs p > 0.71. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation. We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime.

Original language	English (US)
Title of host publication	FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
Publisher	Association for Computing Machinery, Inc
Pages	96-104
Number of pages	9
ISBN (Electronic)	9798400702020
DOIs	https://doi.org/10.1145/3594805.3607134
State	Published - Aug 30 2023
Externally published	Yes
Event	17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2023 - Potsdam, Germany Duration: Aug 30 2023 → Sep 1 2023

Publication series

Name	FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Conference

Conference	17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2023
Country/Territory	Germany
City	Potsdam
Period	8/30/23 → 9/1/23

Bibliographical note

Publisher Copyright:
© 2023 ACM.

Keywords

parameterized complexity
runtime analysis
vertex cover

Access

10.1145/3594805.3607134

OpenUrl availability

Full text

Cite this

Kearney, J., Neumann, F., & Sutton, A. M. (2023). Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers. In FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (pp. 96-104). (FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms). Association for Computing Machinery, Inc. https://doi.org/10.1145/3594805.3607134

Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers. / Kearney, Jack; Neumann, Frank; Sutton, Andrew M.
FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association for Computing Machinery, Inc, 2023. p. 96-104 (FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kearney, J, Neumann, F & Sutton, AM 2023, Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers. in FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, Inc, pp. 96-104, 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2023, Potsdam, Germany, 8/30/23. https://doi.org/10.1145/3594805.3607134

Kearney J, Neumann F, Sutton AM. Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers. In FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association for Computing Machinery, Inc. 2023. p. 96-104. (FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms). doi: 10.1145/3594805.3607134

Kearney, Jack ; Neumann, Frank ; Sutton, Andrew M. / Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers. FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association for Computing Machinery, Inc, 2023. pp. 96-104 (FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms).

@inproceedings{ead40b1174f64b53bdf3c39777e6e026,

title = "Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers",

abstract = "We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every O(n log n) steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs p > 0.71. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation. We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime.",

keywords = "parameterized complexity, runtime analysis, vertex cover",

author = "Jack Kearney and Frank Neumann and Sutton, {Andrew M.}",

note = "Publisher Copyright: {\textcopyright} 2023 ACM.; 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2023 ; Conference date: 30-08-2023 Through 01-09-2023",

year = "2023",

month = aug,

day = "30",

doi = "10.1145/3594805.3607134",

language = "English (US)",

series = "FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms",

publisher = "Association for Computing Machinery, Inc",

pages = "96--104",

booktitle = "FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms",

}

TY - GEN

T1 - Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

AU - Kearney, Jack

AU - Neumann, Frank

AU - Sutton, Andrew M.

PY - 2023/8/30

Y1 - 2023/8/30

N2 - We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every O(n log n) steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs p > 0.71. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation. We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime.

AB - We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every O(n log n) steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs p > 0.71. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation. We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime.

KW - parameterized complexity

KW - runtime analysis

KW - vertex cover

UR - http://www.scopus.com/inward/record.url?scp=85174503029&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85174503029&partnerID=8YFLogxK

U2 - 10.1145/3594805.3607134

DO - 10.1145/3594805.3607134

M3 - Conference contribution

AN - SCOPUS:85174503029

T3 - FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

SP - 96

EP - 104

BT - FOGA 2023 - Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

PB - Association for Computing Machinery, Inc

T2 - 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2023

Y2 - 30 August 2023 through 1 September 2023

ER -

Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this