The language CLIQUE = {〈G, k〉 | G is an undirected graph with a k-clique} was defined on Textbook Theorem 4.24, and then
Posted: Wed Apr 27, 2022 3:44 pm
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
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