<p>Is directed reachability on a graph with bounded diameter (e.g. diameter $O(n^{1/2})$) known to be solvable simultaneously in polynomial time and sublinear space? Is anything known if the diameter is poly-logarithmic?</p>

<p>Informally, is this promise problem when we know the graph has bounded diameter easier to solve in sublinear space? There has been significant work over the past few decades on trying to beat BFS/DFS for restricted graph classes (e.g. planar, bounded-genus graphs [2]), but to the best of my knowledge getting polynomial time and sublinear space simultaneously on general directed graphs remains open [1].</p>

<p>[1] <a href="http://cse.unl.edu/~vinod/papers/reach_survey.pdf" rel="nofollow noreferrer">http://cse.unl.edu/~vinod/papers/reach_survey.pdf</a></p>

<p>[2] <a href="https://www.cse.iitk.ac.in/users/rtewari/papers/highgenus_fsttcs.pdf" rel="nofollow noreferrer">https://www.cse.iitk.ac.in/users/rtewari/papers/highgenus_fsttcs.pdf</a></p>

CC BY-SA 4.0
2018-07-05T22:46:04.623Z
I think this a neat question!!  One small thing to notice is that for graphs with $n$ vertices and diameter $\sqrt{n}$, if we can solve directed reachability in $poly(n)$ time and $o(\sqrt{n})$ space, then I think we could solve the general directed graph reachability in $poly(n)$ time and $o(n)$ space.
Michael Wehar
CC BY-SA 4.0
2018-07-06T00:03:54.990Z
Hi Michael, thanks for your interest and the interesting claim. Unfortunately I don't see how we could reduce general directed graph reachability using a sublinear-space reduction to a bunch of calls to directed reachability on $\sqrt{n}$-diameter bounded graphs. I had some rough ideas about layering into $\sqrt{n}$ layers, but  while such a graph is diameter bounded, it doesn't preserve the transitive closure of the original graph. Intuitively I agree that getting $O(\mathsf{diam}(G))$ space seems like the best one could hope for, but the truth may be much more interesting.
xal
CC BY-SA 4.0
2018-07-06T06:55:42.730Z
Here is my argument, please let me know if I made a mistake.  Suppose that we could solve directed graph reachability for any $n$ vertex directed graph with diameter at most $\sqrt{n}$ in $n^k$ time and $o(\sqrt{n})$ space.  Now, consider an arbitrary graph with $n$ vertices, if we add in $n^2 - n$ isolated vertices, then we have an $n^2$ vertex graph of diameter at most $n$.  Then, we apply the algorithm to solve reachability in $n^{2k}$ time and $o(n)$ space.
Michael Wehar
CC BY-SA 4.0
2018-07-06T06:57:47.063Z
More generally, I think beating $diam(G)$ space will imply that we can beat $n$ space for the general directed graph reachability problem.
Michael Wehar
CC BY-SA 4.0
2018-07-06T23:12:11.817Z
Thanks for updating with the argument! I believe it's correct.
xal
<space-complexity>
Simultaneous time-space complexity of directed reachability on bounded diameter graphs
xal
# Simultaneous time-space complexity of directed reachability on bounded diameter graphs

(Asked by: username_0 on 2018-07-05)

Is directed reachability on a graph with bounded diameter (e.g. diameter $O(n^{1/2})$) known to be solvable simultaneously in polynomial time and sublinear space? Is anything known if the diameter is poly-logarithmic?

Informally, is this promise problem when we know the graph has bounded diameter easier to solve in sublinear space? There has been significant work over the past few decades on trying to beat BFS/DFS for restricted graph classes (e.g. planar, bounded-genus graphs [2]), but to the best of my knowledge getting polynomial time and sublinear space simultaneously on general directed graphs remains open [1].

[1] <http://cse.unl.edu/~vinod/papers/reach_survey.pdf>

[2] <https://www.cse.iitk.ac.in/users/rtewari/papers/highgenus_fsttcs.pdf>

**Tags:** space-complexity

> **Comments:**
> **username_1**: I think this a neat question!!  One small thing to notice is that for graphs with $n$ vertices and diameter $\sqrt{n}$, if we can solve directed reachability in $poly(n)$ time and $o(\sqrt{n})$ space, then I think we could solve the general directed graph reachability in $poly(n)$ time and $o(n)$ space.  
> **username_0**: Hi Michael, thanks for your interest and the interesting claim. Unfortunately I don't see how we could reduce general directed graph reachability using a sublinear-space reduction to a bunch of calls to directed reachability on $\sqrt{n}$-diameter bounded graphs. I had some rough ideas about layering into $\sqrt{n}$ layers, but  while such a graph is diameter bounded, it doesn't preserve the transitive closure of the original graph. Intuitively I agree that getting $O(\mathsf{diam}(G))$ space seems like the best one could hope for, but the truth may be much more interesting.  
> **username_1**: Here is my argument, please let me know if I made a mistake.  Suppose that we could solve directed graph reachability for any $n$ vertex directed graph with diameter at most $\sqrt{n}$ in $n^k$ time and $o(\sqrt{n})$ space.  Now, consider an arbitrary graph with $n$ vertices, if we add in $n^2 - n$ isolated vertices, then we have an $n^2$ vertex graph of diameter at most $n$.  Then, we apply the algorithm to solve reachability in $n^{2k}$ time and $o(n)$ space.  
> **username_1**: More generally, I think beating $diam(G)$ space will imply that we can beat $n$ space for the general directed graph reachability problem.  
> **username_0**: Thanks for updating with the argument! I believe it's correct.  

---

## 0 answers

