Recognizing Maximal Unfrozen Graphs with respect to Independent Sets is CO-NP-complete.
Nesrine AbbasJoseph C. CulbersonLorna StewartPublished in: Discret. Math. Theor. Comput. Sci. (2005)
Keyphrases
- np complete
- polynomial time complexity
- bounded treewidth
- np hard
- randomly generated
- computational complexity
- independent set
- logical equivalence
- graph matching
- satisfiability problem
- constraint satisfaction problems
- graph theory
- pspace complete
- np complete problems
- graph representation
- automatic recognition
- graph theoretic
- graph clustering
- conjunctive queries