@inproceedings{1ba5063356484ca0ae7f1303fc081d93,
title = "Switching Classes: Characterization and Computation",
abstract = "In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class G, we are concerned with the maximum subclass and the minimum superclass of G that are closed under switching. We characterize the maximum subclass for many important classes G, and prove that it is finite when G 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",
author = "Dhanyamol Antony and Yixin Cao and Sagartanu Pal and Sandeep, \{R. B.\}",
note = "Publisher Copyright: {\textcopyright} Dhanyamol Antony, Yixin Cao, Sagartanu Pal, and R. B. Sandeep.; 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 ; Conference date: 26-08-2024 Through 30-08-2024",
year = "2024",
month = aug,
doi = "10.4230/LIPIcs.MFCS.2024.11",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Rastislav Kralovic and Antonin Kucera",
booktitle = "49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024",
address = "Germany",
}