2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    Commented Jul 5, 2018 at 22:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – xal
    Commented Jul 6, 2018 at 0:03
  • $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    Commented Jul 6, 2018 at 6:55
  • 1
    $\begingroup$ More generally, I think beating $diam(G)$ space will imply that we can beat $n$ space for the general directed graph reachability problem. $\endgroup$
    – Michael Wehar
    Commented Jul 6, 2018 at 6:57
  • 1
    $\begingroup$ Thanks for updating with the argument! I believe it's correct. $\endgroup$
    – xal
    Commented Jul 6, 2018 at 23:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.