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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01890534
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

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

77

Files downloads

26