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

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

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

CC BY-SA 4.0
2020-02-21T17:41:07.267Z
There are $|V|^2$ vertex pairs, so are you assuming the number of edges $N = |V|$?
smapers
CC BY-SA 4.0
2020-02-21T22:20:53.697Z
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
CC BY-SA 4.0
2020-02-21T22:40:59.657Z
Is this question specific to the constant 4? Or is it some parameter k? (Which is assumed to be small?)
Laakeri
CC BY-SA 4.0
2020-02-21T22:56:04.927Z
I am interested in all $k$ which are constants. The case of $k=2,3$ are easy to solve and known from existing work - https://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
CC BY-SA 4.0
2020-02-22T06:18:39.950Z
No, a graph with $|V|$ nodes can have $|V|^2$ edges.
smapers
CC BY-SA 4.0
2020-02-22T06:49:47.973Z
Can we use the original input graph for free, or does it also count towards the space bound in your setup?
Emil Jeřábek
CC BY-SA 4.0
2020-02-22T16:06:50.730Z
The input graph also counts towards space. So in this setting, we can assume that we are interested in the regime where $S \geq O(N)$.
karmanaut
CC BY-SA 4.0
2020-02-22T16:08:46.293Z
@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
CC BY-SA 4.0
2020-03-15T05:43:10.837Z
Is the query going to be whether there exists (at least) one path of length (exactly) 4 that joins a pair of vertices? and would u-a-b-a-v count with node 'a'  re-used? (that is, are you limiting to *simple* paths?) Also, I agree with @smapers that your statement of space (a bit for each pair of vertices) just needs |V|^2 and not N^2
JimN
<graph-theory><graph-algorithms><space-time-tradeoff>
Sublinear time path existence
karmanaut
# Sublinear time path existence

(Asked by: username_0 on 2020-02-21)

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!

**Tags:** graph-theory, graph-algorithms, space-time-tradeoff

> **Comments:**
> **username_1**: There are $|V|^2$ vertex pairs, so are you assuming the number of edges $N = |V|$?  
> **username_0**: 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$.  
> **username_2**: Is this question specific to the constant 4? Or is it some parameter k? (Which is assumed to be small?)  
> **username_0**: I am interested in all $k$ which are constants. The case of $k=2,3$ are easy to solve and known from existing work - https://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}$.  
> **username_1**: No, a graph with $|V|$ nodes can have $|V|^2$ edges.  
> **username_3**: Can we use the original input graph for free, or does it also count towards the space bound in your setup?  
> **username_0**: The input graph also counts towards space. So in this setting, we can assume that we are interested in the regime where $S \geq O(N)$.  
> **username_0**: @username_1 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$.  
> **username_4**: Is the query going to be whether there exists (at least) one path of length (exactly) 4 that joins a pair of vertices? and would u-a-b-a-v count with node 'a'  re-used? (that is, are you limiting to *simple* paths?) Also, I agree with @username_1 that your statement of space (a bit for each pair of vertices) just needs |V|^2 and not N^2  

---

## 0 answers

