Switching Classes: Characterization and Computation
<|reference_start|>Switching Classes: Characterization and Computation: In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class $\mathcal{G}$, we are concerned with the maximum subclass and the minimum superclass of $\mathcal{G}$ that are closed under switching. We characterize the maximum subclass for many important classes $\mathcal{G}$, and prove that it is finite when $\mathcal{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-complete 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.<|reference_end|>
@article{antony2024switching,
    title={Switching Classes: Characterization and Computation},
    author={Dhanyamol Antony, Yixin Cao, Sagartanu Pal, R.B. Sandeep},
    journal={arXiv preprint arXiv:2403.04263},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04263},
    primaryClass={cs.DS math.CO}
}