Journal article, Peer reviewed
MetadataShow full item record
Original versionAlgorithmica. 2020, 82 (7), 1859-1880. 10.1007/s00453-020-00677-8
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 G, is there a subgraph complement of G which is in G? We show that this problem can be solved in polynomial time for various choices of the graphs class G, such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is NP-complete when G is the class of regular graphs.