3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What's $V^i$ in the third line? $\endgroup$ – Chris Godsil Jun 13 '13 at 14:28
  • $\begingroup$ $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. $\endgroup$ – rwolst Jun 13 '13 at 14:37
  • $\begingroup$ 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. :) $\endgroup$ – Hagen von Eitzen Jun 13 '13 at 15:27
  • $\begingroup$ 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$. $\endgroup$ – rwolst Jun 13 '13 at 15:42
  • $\begingroup$ But the elements of $V^i$ are $r$-tuples and the arguments to $f$ appear to be sets. $\endgroup$ – Chris Godsil Jun 13 '13 at 15:48
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.