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 G, find a largest clique in GThree 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