# SC^2 algorithms for st-connectivity

Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is a major open problem whether st-connectivity can be solved by a deterministic algorithm in polynomial time and $O({\log}^2{n})$ space i.e., whether $NL \subseteq SC^2$. $RL$, which lies between $L$ and $NL$, is known be in $SC^2$. Hence reachability in directed graphs with polynomial mixing-time is in $SC^2$.

I am looking for special cases of st-connectivity (that are not known to be in $L$) that have $SC^2$ algorithms. Is anything known about planar graphs, planar DAGs ? Note that st-connectivity in DAGs remains NL-complete.

There are two related complexity classes in $\text{NL}$ which are also in $\text{LogDCFL}$, which puts them in $\text{SC}^2$ (by Cook).

• The first is $\text{RUL}$, for "Reach-Unambiguous Log-space" which has reachability in mangroves (graphs where every pair of vertices has at most one directed path between them) as a complete problem. This class has been discussed before.
• The second is $\text{ReachFewL}$, which has reachability complete for graphs with at most a polynomial number of paths between any pair of vertices.

Performing depth-first search on these graphs using a stack has a guarantee that it will take polynomial time, so these classes are in $\text{LogDCFL} \subseteq \text{SC}^2$.

• @Derrick : Please add the references showing that these problems are in LogDCFL. – Shiva Kintali Oct 7 '10 at 22:52
• @Shiva: I thought the last paragraph was an argument that these problems can be recognized by a deterministic pushdown automaton determined by the graph? – András Salamon Oct 7 '10 at 23:40
• @Derrick : Thanks. So there are problems in the intersection of NL and LogDCFL that are not known to be in Logspace. Interesting !! – Shiva Kintali Oct 8 '10 at 21:53
• Yes, very interesting. Again, mangroves have the (log log n) factor of space efficiency over the savitch bound, but I don't know of a similar bound for ReachFewL graphs. – Derrick Stolee Oct 8 '10 at 21:55
• News from COCOON'11: Now $\mathsf{ReachFewL}$ is equal to $\mathsf{ReachUL}$. Woohoo! – Hsien-Chih Chang 張顯之 Aug 14 '11 at 22:31

The last complexity conference showed some progress on this question. Reachability in planar DAGs with $O(\log n)$ sources can be solved in $O(\log n)$ space.

Here is also a recent survey by Allender: "Reachability Problems: An Update"

• It appears that none of the "intermediate" problems (except RL) are known to be in SC^2. – Shiva Kintali Sep 26 '10 at 8:22