# 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. Oct 7, 2010 at 22:52
• @Derrick : Thanks. So there are problems in the intersection of NL and LogDCFL that are not known to be in Logspace. Interesting !! Oct 8, 2010 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. Oct 8, 2010 at 21:55
• The reference for RUL in SC$^2$ is given in Klaus-Jörn Lange, "An unambiguous class possessing a complete set" STACS ’97. Feb 24, 2011 at 0:52
• News from COCOON'11: Now $\mathsf{ReachFewL}$ is equal to $\mathsf{ReachUL}$. Woohoo! Aug 14, 2011 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. Sep 26, 2010 at 8:22
• @ShivaKintali What do you mean by intermediate problems? Nov 25, 2022 at 21:16
• @Turbo Intermediate problems are those whose complexity lies between L and NL. Nov 27, 2022 at 0:54