License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.21
URN: urn:nbn:de:0030-drops-88476
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8847/
Fomin, Fedor V. ;
Golovach, Petr A. ;
Strømme, Torstein J. F. ;
Thilikos, Dimitrios M.
Partial Complementation of Graphs
Abstract
A partial complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there a partial complement of G which is in G? We show that this problem can be solved in polynomial time for various choices of the graphs class G, such as 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.
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs:2018:8847,
author = {Fedor V. Fomin and Petr A. Golovach and Torstein J. F. Str\omme and Dimitrios M. Thilikos},
title = {{Partial Complementation of Graphs}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-068-2},
ISSN = {1868-8969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8847},
URN = {urn:nbn:de:0030-drops-88476},
doi = {10.4230/LIPIcs.SWAT.2018.21},
annote = {Keywords: Partial complementation, graph editing, graph classes}
}
|
Keywords: |
|
Partial complementation, graph editing, graph classes |
|
Collection: |
|
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
