Complexity results for generating subgraphs
From MaRDI portal
Publication:724239
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 434906 (Why is no real title available?)
- scientific article; zbMATH DE number 3614795 (Why is no real title available?)
- A characterization of well covered graphs of girth 5 or greater
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- Complexity of automaton identification from given data
- Complexity results for well‐covered graphs
- Local Structure When All Maximal Independent Sets Have Equal Weight
- Modeling \(k\)-coteries by well-covered graphs
- On relating edges in graphs without cycles of length 4
- Recognizing Greedy Structures
- Some covering concepts in graphs
- The structure of well-covered graphs and the complexity of their recognition problems
- The structure of well-covered graphs with no cycles of length 4
- Weighted well-covered claw-free graphs
- Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\)
- Well covered simplicial, chordal, and circular arc graphs
- Well-Covered Vector Spaces of Graphs
- Well-covered claw-free graphs
- Well-covered graphs without cycles of lengths 4, 5 and 6
Cited in
(8)- Weighted well-covered graphs without cycles of lengths 5, 6 and 7
- Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7
- Recognizing generating subgraphs revisited
- Well-covered graphs with constraints on \(\Delta\) and \(\delta\)
- Well-dominated graphs without cycles of lengths 4 and 5
- An appraisal of the performance of the MMSC subgraph generation algorithm on a Cyber system 170/720
- Generating hinges from arbitrary subhypergraphs
- scientific article; zbMATH DE number 2148180 (Why is no real title available?)
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)
