License
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://drops.dagstuhl.de/opus/volltexte/2018/8847/
Go to the corresponding LIPIcs Volume Portal


Fomin, Fedor V. ; Golovach, Petr A. ; StrÝmme, Torstein J. F. ; Thilikos, Dimitrios M.

Partial Complementation of Graphs

pdf-format:
LIPIcs-SWAT-2018-21.pdf (0.5 MB)


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
Seminar: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 30.05.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI