15
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Derrick : Please add the references showing that these problems are in LogDCFL. $\endgroup$ – Shiva Kintali Oct 7 '10 at 22:52
  • $\begingroup$ @Shiva: I thought the last paragraph was an argument that these problems can be recognized by a deterministic pushdown automaton determined by the graph? $\endgroup$ – András Salamon Oct 7 '10 at 23:40
  • 1
    $\begingroup$ @Derrick : Thanks. So there are problems in the intersection of NL and LogDCFL that are not known to be in Logspace. Interesting !! $\endgroup$ – Shiva Kintali Oct 8 '10 at 21:53
  • 2
    $\begingroup$ 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. $\endgroup$ – Derrick Stolee Oct 8 '10 at 21:55
  • 1
    $\begingroup$ News from COCOON'11: Now $\mathsf{ReachFewL}$ is equal to $\mathsf{ReachUL}$. Woohoo! $\endgroup$ – Hsien-Chih Chang 張顯之 Aug 14 '11 at 22:31
9
$\begingroup$

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"

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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