# 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.

• The elements of $U_1 \times U_2$ are pairs of vertices, and not pairs of sets of vertices. -- Is the source of $f$ perhaps rather meant to be $\mathcal{P}(V) \times \mathcal{P}(V)$, where $\mathcal{P}(V)$ denotes the powerset of $V$? – Stefan Kohl Dec 16 '13 at 15:40
• Ah, yes it is, I'll edit that. – rwolst Dec 16 '13 at 15:43
• I see now that my answer is what was offered on math.SE. It seems to me to settle the question: could you say what else you are hoping for? – Ben Barber Dec 16 '13 at 15:58
• This is simply the upper bound for the problem, I am looking for a bound based on the structure of the graph we are trying to verify, not simply the case for one graph. – rwolst Dec 16 '13 at 16:00

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$.

• In that case yes, but as we know the structure of the graph beforehand and are trying to verify it, there are many graphs for which we can do much better than $(\frac{n}{2})$ – rwolst Dec 16 '13 at 15:58
• Thank you, that clears up my misunderstanding. Perhaps you could make this explicit in the OP? – Ben Barber Dec 16 '13 at 15:59