13
$\begingroup$

Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an expander graph from the original graph, and then do the walk in the expander graph. The expander graph is made by squaring the original graph logarithmically many times. In the expander graph, the diameter is only logarithmic, so a DFS search of logarithmic depth suffices.

Extending the result to $L=NL$ would imply the existence of a logspace algorithm for DSTCON -- the same, but for Directed graphs. (Sometimes just STCON.) My question, maybe slightly soft, is what are the primary obstructions to extending Reingold's proof to that?

It feels slightly like there should be a sort of "directed expander" graph. A similar sort of construction, where you add in edges corresponding to medium-length directed paths, and then some corresponding to long ones; and then you can traverse the graph with logarithmic depth by moving across short paths to get to a long one; then back to short paths at the end.

Is there a major flaw in this concept? Or is it that there aren't any good constructions of such expanders? Or does it somehow require more memory than the undirected version?

I unfortunately cannot find much at all on directed expander graphs. In fact essentially all I could find was https://math.stackexchange.com/questions/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (which is unanswered) and https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . Is there a different term I should be searching under?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
19
$\begingroup$

The central problem is that, on directed graphs, even a truly random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk. The standard counterexample here is a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex, $t$), and each vertex also has an edge leading all the way back to the leftmost vertex, $s$. To get from $s$ to $t$ by a random walk then takes ~$2^n$ time. So, what is the small-space randomized algorithm for directed connectivity that we're hoping to derandomize, analogous to what Reingold did for $USTCON$? (To put it another way, how do we show $RL=NL$, let alone $L=NL$?) For directed connectivity, of course there's Savitch's algorithm, but that takes $O(\log^2 n)$ space, and for general graphs no one has managed to improve it for half a century, with or without the use of randomness.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ For directed connectivity, there is a polynomial-time algorithm using "only" $\frac{n}{2^{\Theta(\sqrt{\log n})}}$ space by Barnes, Buss, Ruzzo and Schieber: A Sublinear space, Polynomial Time Algorithm for Directed s-t Connectivity. It's a clever mix of breadth-first search and a recursive Savitch-like algorithm to find the paths between subsequent levels of the BFS. All that is needed now is to go from $\frac{n}{2^{\Theta(\sqrt{\log n})}}$ to $\log n$. So it hasn't improved, not in half a century, but only in the last 20 years :) $\endgroup$
    – Lieuwe Vinkhuijzen
    Apr 27, 2018 at 10:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.