The Library
Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent
Tools
Tools
Tools
Agrawal, Akanksha, Kanesh, Lawqueen, Lokshtanov, Daniel, Panolan, Fahad, Ramanujan, Maadapuzhi Sridharan, Saurabh, Saket and Zehavi , Meirav (2022) Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent. In: ACM-SIAM Symposium on Discrete Algorithms (SODA22), Virginia, U.S. (virtual conference), 9-12 Jan 2022. Published in: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 1976-2004. ISBN 9781611977073. doi:10.1137/1.9781611977073.79
|
PDF
WRAP-deleting-eliminating-decomposing-hereditary-classes-all-FPT-equivalent-Ramanujan-2022.pdf - Accepted Version - Requires a PDF viewer. Download (1542Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611977073.79
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ℋ.
| Item Type: | Conference Item (Paper) | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Computational complexity | |||||||||||||||||||||||||||
| Series Name: | Proceedings | |||||||||||||||||||||||||||
| Journal or Publication Title: | Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | |||||||||||||||||||||||||||
| Publisher: | SIAM | |||||||||||||||||||||||||||
| ISBN: | 9781611977073 | |||||||||||||||||||||||||||
| Official Date: | 2022 | |||||||||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||||||||
| Page Range: | pp. 1976-2004 | |||||||||||||||||||||||||||
| DOI: | 10.1137/1.9781611977073.79 | |||||||||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||||||||
| Reuse Statement (publisher, data, author rights): | “First Published in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) in 2022, published by the Society for Industrial and Applied Mathematics (SIAM)” “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.” | |||||||||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||||||||
| Conference Paper Type: | Paper | |||||||||||||||||||||||||||
| Title of Event: | ACM-SIAM Symposium on Discrete Algorithms (SODA22) | |||||||||||||||||||||||||||
| Type of Event: | Conference | |||||||||||||||||||||||||||
| Location of Event: | Virginia, U.S. (virtual conference) | |||||||||||||||||||||||||||
| Date(s) of Event: | 9-12 Jan 2022 | |||||||||||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
