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

For a graph class ${\cal H}$, the graph parameters elimination distance to${\cal H}$ (denoted by ${\bf ed}_{\cal H}$) [Bulian and Dawar, Algorithmica,2016], and ${\cal H}$-treewidth (denoted by ${\bf tw}_{\cal H}$) [Eiben et al.JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the"torso" of the graph induced on a modulator to the graph class ${\cal H}$.Here, the torso of a vertex set $S$ in a graph $G$ is the graph with vertex set$S$ and an edge between two vertices $u, v \in S$ if there is a path between$u$ and $v$ in $G$ whose internal vertices all lie outside $S$.  In this paper, we show that from the perspective of (non-uniform)fixed-parameter tractability (FPT), the three parameters described above giveequally powerful parameterizations for every hereditary graph class ${\cal H}$that satisfies mild additional conditions. In fact, we show that for everyhereditary graph class ${\cal H}$ satisfying mild additional conditions, withthe exception of ${\bf tw}_{\cal H}$ parameterized by ${\bf ed}_{\cal H}$, forevery pair of these parameters, computing one parameterized by itself or any ofthe others is FPT-equivalent to the standard vertex-deletion (to ${\cal H}$)problem. As an example, we prove that an FPT algorithm for the vertex-deletionproblem implies a non-uniform FPT algorithm for computing ${\bf ed}_{\cal H}$and ${\bf tw}_{\cal H}$.  The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory,we essentially prove that if ${\cal H}$ is hereditary, union-closed,CMSO-definable, and (a) the canonical equivalence relation (or any refinementthereof) for membership in the class can be efficiently computed, or (b) theclass admits a "strong irrelevant vertex rule", then there exists a uniform FPTalgorithm for ${\bf ed}_{\cal H}$.

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent