# Sublinear time path existence

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!

• There are $|V|^2$ vertex pairs, so are you assuming the number of edges $N = |V|$? – smapers Feb 21 '20 at 17:41
• 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$. – karmanaut Feb 21 '20 at 22:20
• 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}$. – karmanaut Feb 21 '20 at 22:56
• Can we use the original input graph for free, or does it also count towards the space bound in your setup? – Emil Jeřábek Feb 22 '20 at 6:49
• @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$. – karmanaut Feb 22 '20 at 16:08