Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPTEquivalent
Agrawal, Akanksha and Kanesh, Lawqueen and Lokshtanov, Daniel and Panolan, Fahad and et al, . (2022) Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPTEquivalent. In: 33rd Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2022, 9 January 2022 through 12 January 2022, Alexander.
Text
Proceedings_of_the_Annual_ACM_SIAM.pdf  Published Version Restricted to Registered users only Download (1MB)  Request a copy 
Abstract
Vertexdeletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by modℋ) of a modulator to a graph class ℋ, i.e., a set of vertices whose deletion results in a graph in ℋ. 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 ℋ, the graph parameters elimination distance to ℋ (denoted by edℋ) [Bulian and Dawar, Algorithmica, 2016] and ℋtreewidth (denoted by twℋ) [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 ℋ. 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 (nonuniform) fixedparameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of edℋ parameterized by twℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPTequivalent to the standard vertexdeletion (to ℋ) problem. As an example, we prove that an FPT algorithm for the vertexdeletion problem implies a nonuniform FPT algorithm for computing edℋ and twℋ. The conclusions of nonuniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, unionclosed, CMSOdefinable, 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ℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing edℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ 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 nonuniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative. Copyright © 2022 by SIAM.
[error in script]IITH Creators: 



Item Type:  Conference or Workshop Item (Paper)  
Additional Information:  ∗The full version of the paper can be accessed at https://arxiv.org/abs/1902.09310 †Agrawal is supported by New Faculty Initiation Grant IIT Madras. Lokshtanov and Zehavi acknowledge support from United StatesIsrael Binational Science Foundation (BSF) grant no. 2018302. Lokshtanov is also supported by NSF award CCF2008838. Zehavi is also supported by Israel Science Foundation (ISF) grant no. 1176/18. Panolan is supported by Seed grant, IIT Hyderabad (SG/IITH/F224/202021/SG79). Ramanujan is supported by Engineering and Physical Sciences Research Council’s New Investigator Award (EP/V007793/1). Saurabh is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819416); and he also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA01/201718.  
Uncontrolled Keywords:  Condition; Finite number; Fixedparameter tractability; Graph class; Nonuniform; Parameterized; Topologicalminor; Treewidth; Vertex deletion problems; Vertex set  
Subjects:  Computer science  
Divisions:  Department of Computer Science & Engineering  
Depositing User:  . LibTrainee 2021  
Date Deposited:  28 Jul 2022 12:37  
Last Modified:  28 Jul 2022 12:37  
URI:  http://raiith.iith.ac.in/id/eprint/9996  
Publisher URL:  http://doi.org/10.1137/1.9781611977073.79  
Related URLs: 
Actions (login required)
View Item 
Statistics for this ePrint Item 