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?
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
0 comments:
Post a Comment
Let us know your responses and feedback