Problem Detail: 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?
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?
Asked By : badjr
Answered By : Kyle Jones
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7052 3.2K people like this
