Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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:

undirected graph

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?

share|improve this question
1  
$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
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
How did you decide that the lower bound should be 3? –  badjr Nov 30 '12 at 21:17
1  
@deezy If the graph has any edges at all, then it contains a 2-clique, so I didn't see any point in using the oracle for that. But 2 would work as well as 3. –  Kyle Jones Nov 30 '12 at 22:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.