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

  • $\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$ 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