TY - GEN
T1 - Partial complementation of graphs
AU - Fomin, Fedor V.
AU - Golovach, Petr A.
AU - Strømme, Torstein J.F.
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, and Dimitrios M. Thilikos.
PY - 2018/6/1
Y1 - 2018/6/1
N2 - 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.
AB - 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.
KW - Graph classes
KW - Graph editing
KW - Phrases partial complementation
UR - http://www.scopus.com/inward/record.url?scp=85049003427&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049003427&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SWAT.2018.21
DO - 10.4230/LIPIcs.SWAT.2018.21
M3 - Conference contribution
AN - SCOPUS:85049003427
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 211
EP - 2113
BT - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018
A2 - Eppstein, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018
Y2 - 18 June 2018 through 20 June 2018
ER -