Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs

Luke B Branson, Andrew M. Sutton

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 three NP-hard graph problems. For k-VERTEXCOVER, we prove that the (1+1) EA using focused jump-and-repair can find a k-vertex cover (if one exists) in O(2kn2log⁡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!n2log⁡n) iterations in expectation, and for ODDCYCLETRANSVERSAL, we prove the optimization time for the EA is O(3kkmn2log⁡n). For the latter two problems, this constitutes the first parameterized result for any evolutionary algorithm. 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)
Article number113719
JournalTheoretical Computer Science
Volume951
DOIs
StatePublished - Mar 24 2023

Bibliographical note

Funding Information:
The authors acknowledge the Minnesota Supercomputing Institute at the University of Minnesota for providing resources that contributed to the research results reported within this paper. http://www.msi.umn.edu

Publisher Copyright:
© 2023 Elsevier B.V.

Keywords

  • Combinatorial optimization
  • Parameterized complexity
  • Runtime analysis
  • Theory of evolutionary algorithms

Fingerprint

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

Cite this