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

Abstract

For a graph class $\mathcal{H}$, the graph parameters elimination distance to $\mathcal{H}$ (denoted by ${\mathbf{ed}}_{\mathcal{H}}$) [Bulian and Dawar, Algorithmica, 2016], and $\mathcal{H}$-treewidth (denoted by ${\mathbf{tw}}_{\mathcal{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 $\mathcal{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 give equally powerful parameterizations for every hereditary graph class $\mathcal{H}$ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class $\mathcal{H}$ satisfying mild additional conditions, with the exception of ${\mathbf{tw}}_{\mathcal{H}}$ parameterized by ${\mathbf{ed}}_{\mathcal{H}}$, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to $\mathcal{H}$) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ${\mathbf{ed}}_{\mathcal{H}}$ and ${\mathbf{tw}}_{\mathcal{H}}$. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if $\mathcal{H}$ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a "strong irrelevant vertex rule", then there exists a uniform FPT algorithm for ${\mathbf{ed}}_{\mathcal{H}}$.

70 pages, To appear in SODA 2022. arXiv admin note: text overlap with arXiv:2103.09715, arXiv:2105.04660 by other authors