NP-complete problem 1:Clique Clique:Given a graph G and a number k, decide whether G has a clique of size =k. Clique:a complete subgraph. Fact:Clique is in NP. Theorem:If one can solve Clique in polynomial time,then one can also solve 3SAT in polynomial time. So Clique is at least as hard as 3-SAT. Corollary:Clique is NP-complete. 20NP-complete problem 1: Clique ◼ Clique: Given a graph 𝐺 and a number 𝑘, decide whether 𝐺 has a clique of size ≥ 𝑘. ❑ Clique: a complete subgraph. ◼ Fact: Clique is in NP. ◼ Theorem: If one can solve Clique in polynomial time, then one can also solve 3SAT in polynomial time. ❑ So Clique is at least as hard as 3-SAT. ◼ Corollary: Clique is NP-complete. 20