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

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

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.

| cite | improve this answer | |
  • $\begingroup$ Your estimate for the number of $k$-regular graphs is a bit naive (you’re describing the bipartite case), but good bounds are known for values of $k$ which are not too large, and may imply your bound. $\endgroup$ – Yuval Filmus Nov 19 '19 at 19:35
  • $\begingroup$ @YuvalFilmus, oh, good point. That reduces the number of bits by at most a factor of 2, though, I think, so it shouldn't affect the asymptotics. Thanks for catching that. $\endgroup$ – D.W. Nov 19 '19 at 21:15

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.