Complexity results for generating subgraphs

DOI10.1007/S00453-017-0325-1zbMATH Open1392.68192arXiv1401.0294OpenAlexW2964077273MaRDI QIDQ724239FDOQ724239

Vadim E. Levit, David Tankus

Publication date: 25 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Abstract: A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition B_X and B_Y. Then B is generating if there exists an independent set S such that S cup B_X and S cup B_Y are both maximal independent sets of G. A relating edge is a generating subgraph in the restricted case that B = K_{1,1}. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is co-NP-complete. Therefore, deciding whether a subgraph is generating is co-NP-complete as well. In this article we discuss the connections among these problems, provide proofs for NP-completeness for several restricted cases, and present polynomial characterizations for some other cases.

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

Recommendations

• Recognizing generating subgraphs revisited
• Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7
• Well-covered graphs without cycles of lengths 4, 5 and 6
• Complexity results for well‐covered graphs
• scientific article; zbMATH DE number 2148180

zbMATH Keywords

maximal independent setvector spacegenerating subgraphrelating edgeweighted well-covered graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A characterization of well covered graphs of girth 5 or greater
• Some covering concepts in graphs
• Modeling \(k\)-coteries by well-covered graphs
• Well-covered claw-free graphs
• Title not available (Why is that?)
• Recognizing Greedy Structures
• Title not available (Why is that?)
• Complexity of automaton identification from given data
• The structure of well-covered graphs and the complexity of their recognition problems
• Complexity results for well‐covered graphs
• Local Structure When All Maximal Independent Sets Have Equal Weight
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• Well covered simplicial, chordal, and circular arc graphs
• The structure of well-covered graphs with no cycles of length 4
• Well-Covered Vector Spaces of Graphs
• Well-covered graphs without cycles of lengths 4, 5 and 6
• On relating edges in graphs without cycles of length 4
• Weighted well-covered claw-free graphs
• Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)

Cited In (8)

• Well-covered graphs with constraints on \(\Delta\) and \(\delta\)
• Well-dominated graphs without cycles of lengths 4 and 5
• Recognizing Generating Subgraphs Revisited
• Weighted well-covered graphs without cycles of lengths 5, 6 and 7
• Generating hinges from arbitrary subhypergraphs
• Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7
• Title not available (Why is that?)
• An appraisal of the performance of the MMSC subgraph generation algorithm on a Cyber system 170/720

This page was built for publication: Complexity results for generating subgraphs

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