Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/108641
Title: | Switching classes : characterization and computation | Authors: | Antony, D Cao, Y Pal, S Sandeep, RB |
Issue Date: | 2024 | Source: | 49th International Symposium on Mathematical Foundations of Computer Science : MFCS 2024, August 26-30, 2024, Bratislava, Slovakia, p. 11:1 - 11:15 | Abstract: | In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class 𝒢, we are concerned with the maximum subclass and the minimum superclass of 𝒢 that are closed under switching. We characterize the maximum subclass for many important classes 𝒢, and prove that it is finite when 𝒢 is minor-closed and omits at least one graph. For several graph classes, we develop polynomial-time algorithms to recognize the minimum superclass. We also show that the recognition of the superclass is NP-hard for H-free graphs when H is a sufficiently long path or cycle, and it cannot be solved in subexponential time assuming the Exponential Time Hypothesis. | Keywords: | Graph modification Hereditary graph class Minor-closed graph class Switching |
Publisher: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik | DOI: | 10.4230/LIPIcs.MFCS.2024.11 | Rights: | © Dhanyamol Antony, Yixin Cao, Sagartanu Pal, and R. B. Sandeep; licensed under Creative Commons License CC-BY 4.0 (https://creativecommons.org/licenses/by/4.0/legalcode) The following publication Dhanyamol Antony, Yixin Cao, Sagartanu Pal, and R. B. Sandeep. Switching Classes: Characterization and Computation. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) is available at https://doi.org/10.4230/LIPIcs.MFCS.2024.11. |
Appears in Collections: | Conference Paper |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs.MFCS.2024.11.pdf | 718.74 kB | Adobe PDF | View/Open |
Page views
25
Citations as of Sep 22, 2024
Downloads
11
Citations as of Sep 22, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.