Graph Verification Problem Does anyone know whether the following problem has been solved or has an easy solution?
Given a graph $(V,E)$, two subsets of the vertices $U_1=\{u_1, \dots, u_r \}, U_2=\{v_1, \dots, v_s \} \subset V$ and a function $$f: \mathcal{P}(V) \times \mathcal{P}(V) \rightarrow \{0,1\}$$
s.t.
$$
f(\{u_1, \dots, u_r \},  \{v_1, \dots, v_s \}) = 
$$
\begin{cases}
1 & \exists \mbox{ any edge between sets } \{u_1, \dots, u_r \},  \{v_1, \dots, v_s \} \\
0 & \mbox{otherwise}
\end{cases}
where $\mathcal{P}(V)$ denotes the powerset of $V$.
The question then is, what is the best way to repeatedly partition the set $V$, so that we can verify the graph structure (edges between vertices) with the minimum number of calls to $f$.
Note:
If $|V| = p$, an upper bound on the problem is trivially $p(p-1)/2$ by checking every pair of vertices individually.
A lower bound on the problem is $[log_2 p]$ which is deduced by considering an empty graph. Finding a covering of bicliques gives a way to check that graph is empty. 
[We assume that $f(\{v_i\},\{v_i\}) = 1$]
Notes: 
1) This seems close to maybe being reformulated as some sort of weighing problem?
2) I asked the question previously on the Mathematics site but didn't get any conclusive answers. 
Edit:
To be clear, the optimal number of calls will be based on the structure of the graph $(V,E)$ that we are trying to verify. For example the empty graph has an optimal solution equal to the lower bound and a fully connected graph has that of the upper bound. 
What I want is a generalisation e.g. an answer like: "if the graph contain $a$ cliques of size $b$ an upper bound will be $g(a,b)$..." that gets to the heart of the problem.
 A: I am now assuming that the graph $G$ whose structure we are trying to verify is labelled, and that we know the exact position of all the edges we expect to find.
If we get $k$ "yes" answers then we cannot guarantee that $G$ contains more than $k$ edges, as we can pick at most $k$ edges (one for each complete bipartite graph queried) that will ensure that the answers to those questions were "yes".  So we need at least $e(G)$ questions to verify that all the required edges of $G$ are present.
We can work faster on the complement: we need exactly as many questions as it takes complete bipartite graphs to cover the non-edges of $G$.  This is always at most $n$ (check the neighbourhoods in the complement), so verifying the presence of the required edges will usually take longer.
Since most graphs contain a positive fraction of all possible edges, you need $\Theta(n^2)$ queries for a randomly chosen graph on $n$ vertices.  More generally, the number of edges in $G$ will always be the limiting factor until $G$ has $o(n)$ edges, so the answer remains unexciting until $G$ is very sparse indeed.
The earlier answers are preserved below the line.

Edit: this answer covers less ground than the answer on the original math.SE question.

Let $G= K_n^-$ be a clique with one edge $xy$ deleted.  Then the answer to the question "are there any edges between $U_1$ and $U_2$?" is "yes" unless $U_1 = \{x\}$ and $U_2=\{y\}$ (or vice versa).  So even if we know that our graph is a clique with at most one edge deleted we can't do better than $\binom n 2$.
