Partial complementation of graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2018

Partial complementation of graphs


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.
Fichier principal
Vignette du fichier
xsoctratfg.pdf (562.28 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01890534 , version 1 (08-10-2018)




Fedor V. Fomin, Petr A. Golovach, Torstein J F 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⟩
106 View
60 Download



Gmail Mastodon Facebook X LinkedIn More