Subgraph Complementation
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/2727209/Fomin2020_Article_SubgraphComplementation32207.pdf.jpg?sequence=6&isAllowed=y)
View/ Open
Date
2020-02Metadata
Show full item recordCollections
- Department of Informatics [928]
- Registrations from Cristin [9791]
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 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.