<p>I guess Single-source Single-sink Planar DAG (SSPD) reachability has logspace algorithm with a modest running time ($O(n^2)$?). I am not so sure about
Single-source Multiple-sink Planar DAG Reachability (SMPD) algorithm.</p>

<p>Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009)</p>

<p>Also, a new logspace algorithm for planarity testing and embedding runs in modestly polynomial time (modulo undirected reachability, of course)</p>

<p>Ref: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CoRR abs/1101.2637: (2011)</p>

<p>Finally, here is a simple toy problem which has a logspace algo with a modest
running time (modulo undirected reachability) viz. Outerplanar Isomorphism.</p>

CC BY-SA 3.0
2011-07-19T15:16:56.067Z
The SSPD algorithm is $O(n^2)$ after the planar embedding is found and uses the fact that there is are linear-time, log-space walkable "left-most" and "right-most" paths from any vertex to the sink or the source to any vertex (call these "outer" paths). For finding a path from $u$ to $v$, check if the vertices on the outer paths from u to the sink are along the outer paths from the source to v.
Derrick Stolee
CC BY-SA 3.0
2011-07-18T20:00:54.050Z
2011-07-18T20:00:54.050Z
SamiD
<p>This answer is more of a toy problem than a real research problem.</p>

<p>My typical example of a log-space algorithm to give to programmer friends is the following puzzle:</p>

<blockquote>
  <p>Given a linked list of unknown size ($n$) and using a
  constant number of pointer variables,
  determine if the linked list ever
  loops.</p>
</blockquote>

<p>The solution is a log-space algorithm, using two $O(\log n)$-sized pointers to linked list nodes.  Start both at the start of the linked list and perform the following iterative procedure:</p>

<ul>
<li>Advance the first pointer in the list by one step.</li>
<li>Advance the second pointer in the list by two steps.</li>
<li>If either pointer finds the end, return false.</li>
<li>If the nodes point to the same node, return true.</li>
<li>Otherwise, iterate again.</li>
</ul>

<p>This process will eventually terminate.  If there is no loop, it will take $n$ steps.  If there is a loop, the two-step pointer cannot pass the one-step pointer without a collision, and this occurs before the one-step pointer finishes the loop (which is under $n$ steps).</p>

CC BY-SA 2.5
2010-12-01T06:49:25.880Z
Yes. There are many linked list problems (insertion, deletion, merging) that fall in this category. To make things more interesting let's look at problems that are at least $NC^1$-hard.
Shiva Kintali
CC BY-SA 2.5
2010-12-01T06:38:58.317Z
2010-12-01T06:38:58.317Z
Derrick Stolee
<p>The <a href="http://www.google.com/search?q=deutsch%20schorr%20waite%20algorithm" rel="nofollow">Deutsch-Schorr-Waite</a> algorithm is an $O(n)$ graph marking algorithm, variants of which form the heart of many garbage collector implementations. The problem is to mark the nodes of a graph reachable from a root node. The naive recursive traversal needs linear space to hold the stack of visited nodes, but the DSW algorithm encodes that stack by a cunning link reversal trick -- when it follows an edge, it changes the edge it followed to reverse the source and target, so that it can encode the stack in the graph itself. </p>

<p>IIUC, I think this satisfies your $NC^1$ requirement because additional processors don't help you traverse the graph if if it happens to be organized as a linked list. (This is, in fact, a big PITA for practical garbage collection algorithms!) </p>

CC BY-SA 3.0
2011-07-19T15:13:32.587Z
Since you are changing the graph, this is not a log-space algorithm, where the input tape must be read-only. This is an interesting algorithm on its own.
Derrick Stolee
CC BY-SA 3.0
2011-07-19T07:02:24.553Z
2011-07-19T07:02:24.553Z
Neel Krishnaswami
<p>It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, planar graph isomorphism) run in $O(n^k)$ where $k$ is insanely large.</p>

<ul>
<li>I am looking for examples of natural problems that are known to be solvable simultaneously in deterministic logspace and $O(n^k)$ time where $k \leq 10$. There is nothing special about 10. Looking at the currently known logspace algorithms, I think $k \leq 10$ is interesting enough.</li>
<li><a href="http://portal.acm.org/citation.cfm?id=1382621">Aleliunas et al.</a> showed that undirected st-connectivity is in $RL$ (randomized logspace). The running time of their algorithm is $O(n^3)$. Are there natural problems that can be solved simultaneously in $RL$ and linear time (or) near linear time i. e., $O(n{\log}^i{n})$ time ?</li>
</ul>

<p>Edit : To make things more interesting let's look at problems that are at least $NC^1$-hard.</p>

CC BY-SA 2.5
2010-12-01T05:39:10.700Z
Is there any time analysis to the logspace version of Courcelle's theorem? http://www.eccc.uni-trier.de/report/2010/062/
Hsien-Chih Chang 張顯之
<cc.complexity-theory><space-bounded><space-time-tradeoff>
Efficient logspace algorithms
Shiva Kintali
# Efficient logspace algorithms

(Asked by: username_0 on 2010-11-30)

It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, planar graph isomorphism) run in $O(n^k)$ where $k$ is insanely large.

* I am looking for examples of natural problems that are known to be solvable simultaneously in deterministic logspace and $O(n^k)$ time where $k \leq 10$. There is nothing special about 10. Looking at the currently known logspace algorithms, I think $k \leq 10$ is interesting enough.
* [Aleliunas et al.](http://portal.acm.org/citation.cfm?id=1382621) showed that undirected st-connectivity is in $RL$ (randomized logspace). The running time of their algorithm is $O(n^3)$. Are there natural problems that can be solved simultaneously in $RL$ and linear time (or) near linear time i. e., $O(n{\log}^i{n})$ time ?

Edit : To make things more interesting let's look at problems that are at least $NC^1$-hard.

**Tags:** cc.complexity-theory, space-bounded, space-time-tradeoff

> **Comments:**
> **username_1**: Is there any time analysis to the logspace version of Courcelle's theorem? http://www.eccc.uni-trier.de/report/2010/062/  

---

## 3 answers

### Answer by username_2 on 2011-07-18. Score: 10

I guess Single-source Single-sink Planar DAG (SSPD) reachability has logspace algorithm with a modest running time ($O(n^2)$?). I am not so sure about
Single-source Multiple-sink Planar DAG Reachability (SMPD) algorithm.

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009)

Also, a new logspace algorithm for planarity testing and embedding runs in modestly polynomial time (modulo undirected reachability, of course)

Ref: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CoRR abs/1101.2637: (2011)

Finally, here is a simple toy problem which has a logspace algo with a modest
running time (modulo undirected reachability) viz. Outerplanar Isomorphism.

> **Comments:**
> **username_3**: The SSPD algorithm is $O(n^2)$ after the planar embedding is found and uses the fact that there is are linear-time, log-space walkable "left-most" and "right-most" paths from any vertex to the sink or the source to any vertex (call these "outer" paths). For finding a path from $u$ to $v$, check if the vertices on the outer paths from u to the sink are along the outer paths from the source to v.  

---

### Answer by username_3 on 2010-12-01. Score: 9

This answer is more of a toy problem than a real research problem.

My typical example of a log-space algorithm to give to programmer friends is the following puzzle:

> Given a linked list of unknown size ($n$) and using a
> constant number of pointer variables,
> determine if the linked list ever
> loops.

The solution is a log-space algorithm, using two $O(\log n)$-sized pointers to linked list nodes. Start both at the start of the linked list and perform the following iterative procedure:

* Advance the first pointer in the list by one step.
* Advance the second pointer in the list by two steps.
* If either pointer finds the end, return false.
* If the nodes point to the same node, return true.
* Otherwise, iterate again.

This process will eventually terminate. If there is no loop, it will take $n$ steps. If there is a loop, the two-step pointer cannot pass the one-step pointer without a collision, and this occurs before the one-step pointer finishes the loop (which is under $n$ steps).

> **Comments:**
> **username_0**: Yes. There are many linked list problems (insertion, deletion, merging) that fall in this category. To make things more interesting let's look at problems that are at least $NC^1$-hard.  

---

### Answer by username_4 on 2011-07-19. Score: 3

The [Deutsch-Schorr-Waite](http://www.google.com/search?q=deutsch%20schorr%20waite%20algorithm) algorithm is an $O(n)$ graph marking algorithm, variants of which form the heart of many garbage collector implementations. The problem is to mark the nodes of a graph reachable from a root node. The naive recursive traversal needs linear space to hold the stack of visited nodes, but the DSW algorithm encodes that stack by a cunning link reversal trick -- when it follows an edge, it changes the edge it followed to reverse the source and target, so that it can encode the stack in the graph itself.

IIUC, I think this satisfies your $NC^1$ requirement because additional processors don't help you traverse the graph if if it happens to be organized as a linked list. (This is, in fact, a big PITA for practical garbage collection algorithms!)

> **Comments:**
> **username_3**: Since you are changing the graph, this is not a log-space algorithm, where the input tape must be read-only. This is an interesting algorithm on its own.  

---

