# Using Clique decision to solve Clique optimization

How can you perform the clique decision algorithm fewer than $O(n)$ times to solve clique optimization?

I'm not sure if my approach is right but this is my thought process: you would pick vertices in a graph and see if they form a clique, then keep picking more vertices until you have the max possible clique.

I'm not sure how it can be done less than $O(n)$ times.

I can imagine an undirected graph such as: where $\{A, B, C\}$ and $\{B, C, D\}$ would be cliques. The number of vertices is 4, and the number of vertices in the cliques is 3, which is $n - 1$. Would this count as being done in less than $O(n)$ times, or is this the wrong approach to this problem?

• $n - 1$ is not less than $O(n)$. A function $f(n)$ is less than $O(n)$ if $f(n)/n \rightarrow 0$. In your case, $(n-1)/n \rightarrow 1$. – Yuval Filmus Nov 30 '12 at 21:21

You would use binary search. Start with the lower bound being 3 and the upper bound $n$, where $n$ is the number of vertices. Call your clique decision oracle with a $k$ value halfway between the two bounds. If it answers "yes", move your lower bound to $k + 1$. If it answers "no", move your upper bound down to $k - 1$. Repeat until you have found the largest $k$ value the oracle answers "yes" to. It should take $O(\log n)$ calls to the oracle.