2021/04/20 by Akanksha Agrawal, Agrawal, Akanksha, Lawqueen Kanesh +11
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2104.09950
openalex publication_date 2021/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ∈ 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 \cal H that satisfies mild additional conditions. In fact, we show that for every hereditary graph class \cal H satisfying mild additional conditions, with the exception of \bf tw\cal H parameterized by \bf ed\cal 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 \cal H) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem 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 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 \bf ed\cal H.