Subgraph Complementation

Fedor V. Fomin, Petr A. Golovach, Torstein J.F. Strømme, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1859-1880
Number of pages22
Issue number7
StatePublished - Jul 1 2020


  • Graph classes
  • Graph editing
  • Subgraph complementation

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Subgraph Complementation'. Together they form a unique fingerprint.

Cite this