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?
Using Clique decision to solve Clique optimization
algorithms;graph theory;optimization
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.