2026-07-23T03:27:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20567 2024-08-23T05:50:28Z ddc:004 open_access

Switching Classes: Characterization and Computation Antony, Dhanyamol Cao, Yixin Pal, Sagartanu Sandeep, R. B. Switching Graph modification Minor-closed graph class Hereditary graph class 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dhanyamol Antony and Yixin Cao and Sagartanu Pal and R. B. Sandeep 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.11 urn:nbn:de:0030-drops-205678 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode