Subgraph Complementation
Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, Dimitrios M. Thilikos · Algorithmica · 2020
Abstract A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class $${\mathscr {G}}$$ G , is there a subgraph complement of G which is in $${\mathscr {G}}$$ G ? We show that this problem can be solved in polynomial time for various choices of the graphs class $${\mathscr {G}}$$ G , such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is $${{\mathrm{NP}}}$$ NP -complete when $${\mathscr {G}}$$ G is the class of regular graphs.