I’m having trouble coming up with a good adversary strategy for this problem:
Input: a graph G
Output: the maximum size of any clique in G
Where the algorithm asks each time, “are vertices x and y adjacent?” and it could ask about any random pair of vertices in the graph.
So, I need an adversary strategy to force the algorithm to work for as long as possible. Here’s what I have so far:
- for any graph with n vertices, there exists n(n-1)/2 unique vertex pairs the algorithm can ask about
- Adversary could use a grid to keep track of questions asked? Through an adjacency matrix?
I’m kind of stumped on a possible strategy, any help? Would it be better for the adversary to answer “no” to the algorithm, or “yes”?