2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ $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$. $\endgroup$ – Yuval Filmus Nov 30 '12 at 21:21
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How did you decide that the lower bound should be 3? $\endgroup$ – badjr Nov 30 '12 at 21:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Kyle Jones Nov 30 '12 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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