Subgraph complementation

DOI10.1007/S00453-020-00677-8MaRDI QIDQ2182091zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(10)

• Cutting a tree with subgraph complementation is hard, except for some small trees
• On subgraph complementation to \(H\)-free Graphs
• Partial complementation of graphs
• scientific article; zbMATH DE number 19177 (Why is no real title available?)
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Subgraph complementation and minimum rank
• Recognizing some complementary products
• Hamming distance between the strings generated by adjacency matrix of a subgraph complementary graph and their sum
• On subgraph complementation to \(H\)-free graphs
• Algorithms for subgraph complementation to some classes of graphs

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)