Subgraph Complementation

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

doi:10.1007/s00453-020-00677-8

Subgraph Complementation

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

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A subgraph 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 subgraph 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, d-degenerate, or cographs. We complement these results by proving that the problem is NP -complete when G is the class of regular graphs.

Original language	English (US)
Pages (from-to)	1859-1880
Number of pages	22
Journal	Algorithmica
Volume	82
Issue number	7
DOIs	https://doi.org/10.1007/s00453-020-00677-8
State	Published - Jul 1 2020

Keywords

Graph classes
Graph editing
Subgraph complementation

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-020-00677-8

Cite this

@article{0ab46f79fbc843bab274a739c8cb2e03,

title = "Subgraph Complementation",

abstract = "A subgraph 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 subgraph 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, d-degenerate, or cographs. We complement these results by proving that the problem is NP -complete when G is the class of regular graphs.",

keywords = "Graph classes, Graph editing, Subgraph complementation",

author = "Fomin, {Fedor V.} and Golovach, {Petr A.} and Str{\o}mme, {Torstein J.F.} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} 2020, The Author(s).",

year = "2020",

month = jul,

day = "1",

doi = "10.1007/s00453-020-00677-8",

language = "English (US)",

volume = "82",

pages = "1859--1880",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "7",

}

TY - JOUR

T1 - Subgraph Complementation

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

AU - Strømme, Torstein J.F.

AU - Thilikos, Dimitrios M.

PY - 2020/7/1

Y1 - 2020/7/1

N2 - A subgraph 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 subgraph 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, d-degenerate, or cographs. We complement these results by proving that the problem is NP -complete when G is the class of regular graphs.

AB - A subgraph 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 subgraph 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, d-degenerate, or cographs. We complement these results by proving that the problem is NP -complete when G is the class of regular graphs.

KW - Graph classes

KW - Graph editing

KW - Subgraph complementation

UR - http://www.scopus.com/inward/record.url?scp=85078926576&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85078926576&partnerID=8YFLogxK

U2 - 10.1007/s00453-020-00677-8

DO - 10.1007/s00453-020-00677-8

M3 - Article

AN - SCOPUS:85078926576

SN - 0178-4617

VL - 82

SP - 1859

EP - 1880

JO - Algorithmica

JF - Algorithmica

IS - 7

ER -

Subgraph Complementation

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this