2026-07-26T19:18:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8847 2024-03-06T10:42:47Z ddc:004 open_access

Partial Complementation of Graphs Fomin, Fedor V. Golovach, Petr A. Strømme, Torstein J. F. Thilikos, Dimitrios M. Partial complementation graph editing graph classes A partial 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 partial 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, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when G is the class of r-regular graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Torstein J. F. Strømme and Dimitrios M. Thilikos 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.21 urn:nbn:de:0030-drops-88476 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.21 eng https://creativecommons.org/licenses/by/3.0/legalcode