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.