Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I want to prove that if P = NP, then there is a polynomial time algorithm for finding the largest clique in an undirected graph.
I understand how to use a verifier to find this but my issue is since P = NP it doesn't want me to use a verifier. I'm not sure how to approach this.
Assuming $P=NP$, then $CLIQUE \in P$, so you can test for a clique of size $k$ in polynomial time for all $k$. So you can just test for a clique of each size between $1$ and $n$ where $n$ is the number of nodes.
Now that you have the max clique size, you just need to find it. You can do that by removing an abitrary node, then re-running then seeing if there still exists a clique of max size. You will be left with the max size clique.
