Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems

Luke Branson, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Repair operators are often used for constraint handling in constrained combinatorial optimization. We investigate the (1+1) EA equipped with a tailored jump-and-repair operation that can be used to probabilistically repair infeasible offspring in graph problems. Instead of evolving candidate solutions to the entire graph, we expand the genotype to allow the (1+1) EA to develop in parallel a feasible solution together with a growing subset of the instance (an induced subgraph). With this approach, we prove that the EA is able to probabilistically simulate an iterative compression process used in classical fixed-parameter algorithmics to obtain a randomized FPT performance guarantee on two NP-hard graph problems. For k-VertexCover, we prove that the (1+1) EA using focused jump-and-repair can find a k-cover (if one exists) in O(2k n2 log n) iterations in expectation. This leads to an exponential (in k) improvement over the best-known parameterized bound for evolutionary algorithms on VertexCover. For the k-FeedbackVertexSet problem in tournaments, we prove that the EA finds a feasible feedback set in O(2kk!n2 log n) iterations in expectation. This is the first parameterized result for an evolutionary algorithm on this problem. We discuss how to generalize the framework to other parameterized graph problems closed under induced subgraphs and report experimental results that illustrate the behavior of the algorithm on a concrete instance class.

Original languageEnglish (US)
Title of host publicationFOGA 2021 - Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450383523
DOIs
StatePublished - Sep 6 2021
Event16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2021 - Virtual, Online, Austria
Duration: Sep 6 2021Sep 8 2021

Publication series

NameFOGA 2021 - Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Conference

Conference16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2021
Country/TerritoryAustria
CityVirtual, Online
Period9/6/219/8/21

Bibliographical note

Publisher Copyright:
© 2021 ACM.

Keywords

  • combinatorial optimization
  • constraint handling
  • iterative compression
  • parameterized complexity
  • runtime analysis

Fingerprint

Dive into the research topics of 'Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems'. Together they form a unique fingerprint.

Cite this