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

Agrawal, Akanksha and Kanesh, Lawqueen and Lokshtanov, Daniel and Panolan, Fahad and et al, . (2022) Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent. In: 33rd Annual ACM-SIAM 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

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ℋ) 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 (non-uniform) fixed-parameter 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 FPT-equivalent to the standard vertex-deletion (to ℋ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing edℋ and twℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ 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ℋ. 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 non-uniform 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:

IITH Creators	ORCiD
Panolan, Fahad	https://orcid.org/0000-0001-6213-8687

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 States-Israel 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/2020-21/SG-79). 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/MSA-01/2017-18.

Uncontrolled Keywords:

Condition; Finite number; Fixed-parameter tractability; Graph class; Non-uniform; Parameterized; Topological-minor; Tree-width; 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://raiithold.iith.ac.in/id/eprint/9996