1
$\begingroup$

Let $G$ be a $k$-regular graph (each vertex have a degreee $k$). It is trivial to store the graph in $O(\log n)$ space or words such that $j$th neighbour of any vertex can be found in $O(\log n)$ time. Assume that neighbours of each vertex are ordered.

Note that $k=O(\log n)$

Is there an representation of graph $G$ that takes $o(nk)$ space in words such that query can be solved in $O(1)$

$\endgroup$
  • $\begingroup$ Just for my own curiosity, what is this trivial representation you talk about? $\endgroup$ – Tassle Oct 20 at 13:19
  • $\begingroup$ @Tassle either using adjacency list or array. $\endgroup$ – Print_lol Oct 20 at 15:09
0
$\begingroup$

No. Even ignoring the requirement to answer queries, you can't store such a graph in $o(nk)$ space, assuming each word is $\Theta(\lg n)$ bits long (i.e., each word has space to store the index of a single vertex).

In particular, there are ${n-1 \choose k}$ ways to choose $k$ neighbors of a single vertex, so there are ${n-1 \choose k}^n$ possible $k$-regular graphs. Now

$$\lg {n-1 \choose k}^n = n \lg {n-1 \choose k} = kn \lg(n/k) + \Theta(kn) = \Omega(kn \lg(n/k)).$$

Thus, information-theoretically, you need at least $\Omega(kn \lg(n/k))$ bits to store such a graph, or equivalently, at least $\Omega(kn \lg(n/k)/\lg n)$ words. Notice that for $k=O(\log n)$, we have $\lg(n/k)/\lg n = \Theta(1)$.

Therefore, we find that we need at least $\Omega(kn)$ words just to represent all possible $k$-regular graphs, so there is no hope for a data structure with space complexity $o(kn)$, even if you ignore the query time requirement.

$\endgroup$

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.