Abstract
A \emph{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 $\mathcal{G}$, is there a subgraph complement of $G$ which is in $\mathcal{G}$? We show that this problem can be solved in polynomial time for various choices of the graphs class $\mathcal{G}$, such as bipartite, $d$-degenerate, or cographs. We complement these results by proving that the problem is \classNP-complete when $\mathcal{G}$ is the class of regular graphs.