Partial complementation of graphs

Fedor Fomin 1 Petr Golovach 1 Torstein Strømme 1 Dimitrios M. Thilikos 2, 3
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A partial complement of the graph G is a graph obtained from graph G by complementing edges of some of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is it possible to partially complement G to G? We show that this problem can be solved in polynomial time for various classes of graphs like 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.
Complete list of metadatas
Contributor : Dimitrios M. Thilikos <>
Submitted on : Monday, October 8, 2018 - 4:53:15 PM
Last modification on : Thursday, November 15, 2018 - 8:26:05 PM
Long-term archiving on : Wednesday, January 9, 2019 - 3:11:20 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Fedor Fomin, Petr Golovach, Torstein Strømme, Dimitrios M. Thilikos. Partial complementation of graphs. SWAT: Scandinavian Workshops on Algorithm Theory, Jun 2018, Malmö, Sweden. pp.21:1--21:13, ⟨10.4230/LIPIcs.SWAT.2018.21⟩. ⟨lirmm-01890534⟩



Record views


Files downloads