2024/03/07 by Antony, Dhanyamol, Cao, Yixin, Pal, Sagartanu +1 · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.04263
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-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.