Paper Info
Title
Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems
Abstract
ABSTRACTRepair 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.
Year
DOI
Venue
2021
10.1145/3450218.3477304
FOGA
Keywords
DocType
Citations 
runtime analysis, parameterized complexity, iterative compression, combinatorial optimization, constraint handling
Conference
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Luke Branson100.34
Andrew Sutton2206.82