The language CLIQUE = {〈G, k〉 | G is an undirected graph with a
k-clique} was defined on Textbook Theorem 4.24, and then shown in
Corollary 7.43 to be NP-complete. Consider the following language,
which “hard-codes” the value k: 6-CLIQUE = {〈G〉 | G is an
undirected graph with a 6- clique}. Can 6-CLIQUE be decided in
polynomial time? Be clear in your answer (it might not be just
“yes” or “no”), and fully justify your answer
The language CLIQUE = {〈G, k〉 | G is an undirected graph with a k-clique} was defined on Textbook Theorem 4.24, and then
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
The language CLIQUE = {〈G, k〉 | G is an undirected graph with a k-clique} was defined on Textbook Theorem 4.24, and then
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!