Skip to Main content Skip to Navigation
Conference papers

Partial complementation of graphs

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

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01890534
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, October 8, 2018 - 4:53:15 PM
Last modification on : Tuesday, June 30, 2020 - 3:34:02 PM
Document(s) archivé(s) le : Wednesday, January 9, 2019 - 3:11:20 PM

File

xsoctratfg.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

117

Files downloads

41