SC^2 algorithms for st-connectivity

Question

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.

score 12 · Answer 1 · edited Nov 29 '22 at 08:10

12

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"

edited Nov 29 '22 at 08:10

answered Sep 25 '10 at 20:05

Ryan Williams

27,465
7
115
164

It appears that none of the "intermediate" problems (except RL) are known to be in SC^2. – Shiva Kintali Sep 26 '10 at 08:22
@ShivaKintali What do you mean by intermediate problems? – Turbo Nov 25 '22 at 21:16
1

@Turbo Intermediate problems are those whose complexity lies between L and NL. – Shiva Kintali Nov 27 '22 at 00:54

score 12 · Accepted Answer · edited Apr 13 '17 at 12:32

12

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$.

edited Apr 13 '17 at 12:32

Community

1

answered Oct 07 '10 at 22:23

Derrick Stolee

2,044
1
21
34

@Derrick : Please add the references showing that these problems are in LogDCFL. – Shiva Kintali Oct 07 '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 07 '10 at 23:40
@András : Yes. I am just curious about the references. They might have connections to other problems and other insights. – Shiva Kintali Oct 08 '10 at 01:20
I'm not sure about an original reference for showing they are in LogDCFL, because the proof is one line. – Derrick Stolee Oct 08 '10 at 03:33
1

@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 08 '10 at 21:53
2

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 08 '10 at 21:55
1

The reference for RUL in SC$^2$ is given in Klaus-Jörn Lange, "An unambiguous class possessing a complete set" STACS ’97. – Derrick Stolee Feb 24 '11 at 00:52
2

News from COCOON'11: Now $\mathsf{ReachFewL}$ is equal to $\mathsf{ReachUL}$. Woohoo! – Hsien-Chih Chang 張顯之 Aug 14 '11 at 22:31

SC^2 algorithms for st-connectivity

2 Answers2

Linked