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”?


1 Answer 1


Following is a simple adversary strategy that makes the algorithm make $\frac{n(n-1)}{2}$ queries:

For every pair $(x,y)$, adversary answers "no", i.e., $x$ and $y$ are not adjacent.

Proof: Since the adversary is maintaining an empty graph, the answer is trivially a clique of size $0$. However, if the algorithm says "$0$" before making all $\frac{n(n-1)}{2}$ queries, then for any non-queried vertex pair $(x,y)$ the adversary can make $x$ and $y$ adjacent; hence forming a clique of size $2$, and thus proving the algorithm wrong.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.