3
$\begingroup$

Let $G$ be a graph such that $V$ denotes a vertex set and $E$ is an edge set of the graph $G$. Let us consider that for the input graph $G$ it is the case that $|E| \le O(|V| \log |V|)$. Given a graph $G$, I want to answer whether $(u,v) \in E$. If the input graph is given by adjacency representation then I can answer whether $(u,v) \in E$ in $O(\log |V|)$ time with space complexity $O(|V| \log |V|)$.

Space complexity refers to the space taken by input in words. One word means $O(\log |V|)$ bits.

Question: Does there exists a representation of graph $G$ such that I can answer whether $(u,v) \in E$ in $o(\log |V|)$ time with space complexity $O(|V|)$?

$\endgroup$
1
$\begingroup$

Farzan and Monroe, Succinct Representations of Arbitrary Graphs, give such a representation with constant query time. See their Theorem 8.

$\endgroup$

Your Answer

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