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 -