English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Repair operators are often used for constraint handling in constrainedcombinatorial optimization. We investigate the (1+1)~EA equipped with atailored jump-and-repair operation that can be used to probabilistically repairinfeasible offspring in graph problems. Instead of evolving candidate solutionsto the entire graph, we expand the genotype to allow the (1+1)~EA to develop inparallel a feasible solution together with a growing subset of the instance (aninduced subgraph). With this approach, we prove that the EA is able toprobabilistically simulate an iterative compression process used in classicalfixed-parameter algorithmics to obtain a randomized FPT performance guaranteeon 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(2^k n^2\log n)$ iterations in expectation. This leads to an exponential (in$k$) improvement over the best-known parameterized bound for evolutionaryalgorithms on VertexCover. For the $k$-FeedbackVertexSet problem intournaments, we prove that the EA finds a feasible feedback set in$O(2^kk!n^2\log n)$ iterations in expectation, and for OddCycleTransversal, weprove the optimization time for the EA is $O(3^k k m n^2\log n)$. For thelatter two problems, this constitutes the first parameterized result for anyevolutionary algorithm. We discuss how to generalize the framework to otherparameterized graph problems closed under induced subgraphs and reportexperimental results that illustrate the behavior of the algorithm on aconcrete instance class.

Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems Closed Under Induced Subgraphs