# 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$]

• What's $V^i$ in the third line? – Chris Godsil Jun 13 '13 at 14:28
• $V^i = V \times V \times \dots \times V$ $i$ times i.e. it's elements are the sets of $i$ vertices from $V$. I see how this can be confusing as the indices $i$ and $j$ below it refer to different values. I will change this now. – rwolst Jun 13 '13 at 14:37
• I don't get the lower bound. Won't $f(\{v_1,\ldots,v_p\},\{v_1,\ldots,v_p\})=0$ immediately tell us that $E=\emptyset$? Th einformation theory lower bound is that we need to be able to distinguish $2^{p\choose 2}$ graphs, hence need ${p\choose 2}$ bits of information. This coincides with the upper bound. :) – Hagen von Eitzen Jun 13 '13 at 15:27
• I am assuming $f(\{v_1\}, \{v_1\}) = 1$. Therefore $f(\{v_i \}, V-\{v_i\})= 0$ for $i=1\dots (p-1)$ will work for $E = \emptyset$. – rwolst Jun 13 '13 at 15:42
• But the elements of $V^i$ are $r$-tuples and the arguments to $f$ appear to be sets. – Chris Godsil Jun 13 '13 at 15:48

## 1 Answer

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.

• Thanks for the empty graph/lower bound correction. – rwolst Nov 4 '13 at 18:24