Subgraph complementation

DOI10.1007/S00453-020-00677-8zbMATH Open1439.05212arXiv1804.10920OpenAlexW2798301280MaRDI QIDQ2182091FDOQ2182091

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

Publication date: 21 May 2020

Published in: Algorithmica (Search for Journal in Brave)

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 $mathcalG$, is there a partial complement of $G$ which is in $mathcalG$? We show that this problem can be solved in polynomial time for various choices of the graphs class $mathcalG$, such as bipartite, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when $mathcalG$ is the class of $r$-regular graphs.

Full work available at URL: https://arxiv.org/abs/1804.10920

Recommendations

• Subgraph complementation and minimum rank
• Partial complementation of graphs
• Subgraph detection
• Partitioning a graph into complementary subgraphs
• Partitioning a graph into complementary subgraphs
• scientific article; zbMATH DE number 5532174
• Full subgraphs
• Complete subgraphs in multipartite graphs
• scientific article; zbMATH DE number 3906536
• Graph reconstruction from subgraphs

zbMATH Keywords

graph classesgraph editingsubgraph complementation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Recent developments on graphs of bounded clique-width
• Rank-width and vertex-minors
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• The splittance of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• List Partitions
• Recognizing locally equivalent graphs
• Finding Branch-Decompositions and Rank-Decompositions
• Title not available (Why is that?)
• Complexity of hypergraph coloring and Seidel's switching.
• Partial complementation of graphs
• Rank-width: algorithmic and structural results
• On Switching to H‐Free Graphs
• Title not available (Why is that?)
• Parameterized problems related to Seidel's switching
• On the hardness of switching to a small number of edges

Cited In (9)

• Title not available (Why is that?)
• On subgraph complementation to \(H\)-free graphs
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Subgraph complementation and minimum rank
• Algorithms for subgraph complementation to some classes of graphs
• On subgraph complementation to \(H\)-free Graphs
• Hamming distance between the strings generated by adjacency matrix of a subgraph complementary graph and their sum
• Recognizing some complementary products

This page was built for publication: Subgraph complementation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182091)