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

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by mod H ) of a modulator to a graph class H, i.e., a set of vertices whose deletion results in a graph in H. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class H, the graph parameters elimination distance to H (denoted by ed H ) [Bulian and Dawar, Algorithmica, 2016], and H-treewidth (denoted by tw 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 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 ∈ 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 H that satisfies mild additional conditions. In fact, we show that for every hereditary graph class H satisfying mild additional conditions, with the exception of tw H parameterized by ed 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 H) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ed H and tw H .

The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if 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 ed H . Using these sufficient conditions, we obtain uniform FPT algorithms for computing ed H , when H is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when H is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when H is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative.