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. In the restricted case that a generating subgraph B is isomorphic to \(K_{1,1}\), the unique edge in B is called a relating edge. 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 NP-complete. Therefore, deciding whether a subgraph is generating is 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Brown, J.I., Nowakowski, R.J.: Well covered vector spaces of graphs. SIAM J. Discrete Math. 19, 952–965 (2006)
Brown, J.I., Nowakowski, R.J., Zverovich, I.E.: The structure of well-covered graphs with no cycles of length 4. Discrete Math. 307, 2235–2245 (2007)
Caro, Y., Ellingham, N., Ramey, G.F.: Local structure when all maximal independent sets have equal weight. SIAM J. Discrete Math. 11, 644–654 (1998)
Caro, Y., Sebő, A., Tarsi, M.: Recognizing greedy structures. J. Algorithms 20, 137–156 (1996)
Chvatal, V., Slater, P.J.: A note on well-covered graphs. In: Quo Vadis, Graph Theory? Annals of Discrete Mathematics 55, pp. 179–182. North Holland, Amsterdam (1993)
Finbow, A., Hartnell, B., Nowakowski, R.: A characterization of well-covered graphs of girth 5 or greater. J. Comb. Theory B 57, 44–68 (1993)
Finbow, A., Hartnell, B., Nowakowski, R.: A characterization of well-covered graphs that contain neither 4- nor 5-cycles. J. Graph Theory 18, 713–721 (1994)
Gold, E.M.: Complexity of automaton identification from given data. Inf. Control 37, 302–320 (1978)
Levit, V.E., Tankus, D.: Weighted well-covered graphs without \(C_{4}\), \(C_{5}\), \(C_{6}\), \(C_{7}\). Discrete Appl. Math. 159, 354–359 (2011)
Levit, V.E., Tankus, D.: On relating edges in graphs without cycles of length 4. J. Discrete Algorithms 26, 28–33 (2014)
Levit, V.E., Tankus, D.: Weighted well-covered claw-free graphs. Discrete Math. 338, 99–106 (2015)
Levit, V.E., Tankus, D.: Well-covered graphs without cycles of lengths 4, 5 and 6. Discrete Appl. Math. 186, 158–167 (2015)
Plummer, M.D.: Some covering concepts in graphs. J. Comb. Theory 8, 91–98 (1970)
Prisner, E., Topp, J., Vestergaard, P.D.: Well-covered simplicial, chordal and circular arc graphs. J. Graph Theory 21, 113–119 (1996)
Ravindra, G.: Well-covered graphs. J. Comb. Inf. Syst. Sci. 2, 20–21 (1977)
Sankaranarayana, R.S., Stewart, L.K.: Complexity results for well-covered graphs. Networks 22, 247–262 (1992)
Tankus, D., Tarsi, M.: Well-covered claw-free graphs. J. Comb. Theory B 66, 293–302 (1996)
Tankus, D., Tarsi, M.: The structure of well-covered graphs and the complexity of their recognition problems. J. Comb. Theory B 69, 230–233 (1997)
Yamashita, M., Kameda, T.: Modeling k-coteries by well-covered graphs. Networks 34, 221–228 (1999)
Acknowledgements
We wish to thank the anonymous reviewers for their comments. Our special gratitude is to the reviewer that brought to our attention the paper [8], where the MONOTONE SAT problem had been discussed first.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Levit, V.E., Tankus, D. Complexity Results for Generating Subgraphs. Algorithmica 80, 2384–2399 (2018). https://doi.org/10.1007/s00453-017-0325-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-017-0325-1