Three Forms of CLIQUE Usually,it's enough to consider Decision Problem Decision Problem in complexity theory Given a graph G and a number k,decide whether G has a clique of size≥k ↓no harder than Search Problem Given a graph G and a number k,find a clique with size k in G if one exists,else return it doesn't exist ↓no harder than Optimization Problem Given a graph 6,find a largest clique in G 4Three Forms of CLIQUE Decision Problem Given a graph G and a number k, decide whether G has a clique of size ≥ k Search Problem Given a graph G and a number k, find a clique with size ≥ k in G if one exists, else return it doesn’t exist Optimization Problem Given a graph G, find a largest clique in G no harder than no harder than Usually, it’s enough to consider Decision Problem in complexity theory 4