Skip to Main content Skip to Navigation
Conference papers

Partial complementation of graphs

Fedor V. Fomin 1 Petr A. Golovach 1 Torstein Strømme 1 Dimitrios M. Thilikos 2
2 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 metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Monday, October 8, 2018 - 4:53:15 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 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 V. Fomin, Petr A. 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