Graph Verification Problem Does anyone know whether the following problem has been tackled in Graph theory literature:
Given a graph $(V,E)$, two subsets of the vertices $U_1, U_2 \subset V$ and a function $$f: U_1 \times U_2 \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}
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 finding a covering of bicliques and this gives a way to check that graph is empty. 
[We assume that $f(\{v_i\},\{v_i\}) = 1$]
 A: For $K_n$ and $K_n - e$ (where $K_n$ is complete graph on $n$ vertices and $K_n - e$ is complete graph with one edge missing) you need at least $\frac{n(n-1)}2$ calls of $f$ to get all edges since there is no other way to check that each possible edge with at most one exception is present. Any call to $f(U, V)$ with $|U|+|V| > 2$ gives you answer $1$ and no other information than there is at least one edge of $|U|\cdot|V|$ edges between two sets of vertices. Information about any $|U|\cdot|V| - 1$ of these edges at least one of which exists would not give any information about remaining edge. So in this case $\frac{n(n-1)}2$ is best possible solution.
It think there should be something better for sparse graphs at the expense of some extra calls for dense ones. Really any call of $f(U, V)$ for $|U|+|V|>2$ before an absent edge is found would obviously increase total number of call for complete or almost completer graph.
BTW for empty graph on $n$ vertices it's enough to make  $\lceil \log_2 n\rceil$ calls, not even $n - 1$.
It is easy to cover complete graph by $\lceil \log_2 n\rceil$ bicliques and using this covering gives a way to check that graph is empty. Let $n$ be $8$.
Getting $f\big(\{\,v_1, v_2, v_3, v_4\,\}, \{\,v_5, v_6, v_7, v_8\,\}\big) = 0$,
$f\big(\{\,v_1, v_2, v_5, v_6\,\}, \{\,v_3, v_4, v_7, v_8\,\}\big) = 0$ and
$f\big(\{\,v_1, v_3, v_5, v_7\,\}, \{\,v_2, v_4, v_6, v_8\,\}\big) = 0$ we see that there are no edges.
