8
$\begingroup$

Consider a graph $G = (V,E)$ with $N$ edges. Consider two vertices $u_1, v_1 \in V$. We wish to find whether there exists a path of length $4$ between these two vertices or not. This is easy to do in $O(N)$ time by performing a BFS.

Clearly, there also exists a tradeoff between preprocessing space and answering time. I can use $N^2$ space by storing a bit for all possible vertex pairs to indicate whether there exists a path of length $4$ or not and answer each query in constant time. The other end of the spectrum is that BFS gives linear query time.

I am interested in using the least amount of space to answer the query for any pair of vertices $u_1$ and $v_1$. in sublinear time $N^{1-\epsilon}$. Any leads/papers/ideas appreciated!

$\endgroup$
9
  • $\begingroup$ There are $|V|^2$ vertex pairs, so are you assuming the number of edges $N = |V|$? $\endgroup$ – smapers Feb 21 '20 at 17:41
  • $\begingroup$ Yes. The input to the problem is the graph with $N$ edges which implies that size of domain of $V$ is also as large as $N$. $\endgroup$ – karmanaut Feb 21 '20 at 22:20
  • 1
    $\begingroup$ I am interested in all $k$ which are constants. The case of $k=2,3$ are easy to solve and known from existing work - arxiv.org/pdf/1706.05847.pdf (lemma 3). But the tradeoff is clearly not optimal since it is useless when $T = \Omega(N)$. $k=4$ is the first value where I cannot show that $S=N^{1+\epsilon}$ when answering time $T = N^{1-\epsilon}$. $\endgroup$ – karmanaut Feb 21 '20 at 22:56
  • 2
    $\begingroup$ Can we use the original input graph for free, or does it also count towards the space bound in your setup? $\endgroup$ – Emil Jeřábek Feb 22 '20 at 6:49
  • 1
    $\begingroup$ @smapers yes but I am counting the input as the number of edges. In general, the size of the graph is $|E| + |V|$ but assume that $|V| \leq N$ and the input to the problem is of size $N$. $\endgroup$ – karmanaut Feb 22 '20 at 16:08

Your Answer

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

Browse other questions tagged or ask your own question.