2021/06/02 by Weishaupt, Robin, Rothe, Jörg
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2106.01496
Frei et al. [6] showed that the problem to decide whether a graph is stable with respect to some graph parameter under adding or removing either edges or vertices is Θ2P-complete. They studied the common graph parameters α (independence number), β (vertex cover number), ω (clique number), and χ (chromatic number) for certain variants of the stability problem. We follow their approach and provide a large number of polynomial-time algorithms solving these problems for special graph classes, namely for graphs without edges, complete graphs, paths, trees, forests, bipartite graphs, and co-graphs.