patternMinor
Cycles in hardness of ST-CON for the class NL
Viewed 0 times
thehardnessconforclasscycles
Problem
It seems to me that the problem of $s$, $t$ connectivity in a DAG should still be NL-Complete.
I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction is still in NL, but I believe hardness follows as well:
For a turing machine that runs in space $s(n)$, its configuration graph is of size $2^{O(s(n))}$. Furthermore, this implies the time for an NL machine to solve any problem, if it halts at all, is also $2^{O(s(n))}$. Then you can blow up the configuration graph by including a counter for any possible time step a configuration is reached, resulting in a graph of size $2^{O(s(n))} \cdot 2^{O(s(n))} = 2^{O(s(n))}$. At this point the typical reduction to ST-CON can be used since the graph is the same size.
If this is true, then I do not understand why the result SL = L did not follow trivially from the formulation of SL. Namely, an undirected acyclic graph is a tree, and a simple maze algorithm can determine $s$, $t$ connectivity in log-space (and linear time!).
Another strange implication would be that the cyclic or non-cyclic versions of $s$, $t$ connectivity on directed or undirected graphs are equivalent for log-space computation. This implies a simple algorithm like the tree-based one for $s$, $t$ connectivity on a generic undirected graph.
I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction is still in NL, but I believe hardness follows as well:
For a turing machine that runs in space $s(n)$, its configuration graph is of size $2^{O(s(n))}$. Furthermore, this implies the time for an NL machine to solve any problem, if it halts at all, is also $2^{O(s(n))}$. Then you can blow up the configuration graph by including a counter for any possible time step a configuration is reached, resulting in a graph of size $2^{O(s(n))} \cdot 2^{O(s(n))} = 2^{O(s(n))}$. At this point the typical reduction to ST-CON can be used since the graph is the same size.
If this is true, then I do not understand why the result SL = L did not follow trivially from the formulation of SL. Namely, an undirected acyclic graph is a tree, and a simple maze algorithm can determine $s$, $t$ connectivity in log-space (and linear time!).
Another strange implication would be that the cyclic or non-cyclic versions of $s$, $t$ connectivity on directed or undirected graphs are equivalent for log-space computation. This implies a simple algorithm like the tree-based one for $s$, $t$ connectivity on a generic undirected graph.
Solution
It turns out st-connectivity on a general digraph is log-space mapping reducible to st-connectivity on a DAG. Here is the reduction:
Given a directed graph $G$ of size $n$ and two vertices $s$ and $t$, first create a graph $G'$ by making $n$ copies of every vertex $u$ in $G$ as the new vertex $(u, i)$ in $G'$, where $i$ goes from $1$ to $n$ for the respective copies. Then, represent each edge $(u, v)$ in $G'$ by the transition $(u, i) \mapsto (v, i+1)$. Since any path from $s$ to $t$ is of length at most $n$, it then follows that a path from $s$ to $t$ exists in $G$ if and only if it exists in $G'$. Furthermore, since $i$ is always increasing in $(u, i)$, it is clear $G'$ is a DAG. Finally, the mapping can be computed in logarithmic space.
However, the approach does not work for undirected graphs, because cycles can occur in the layering technique. So although st-connectivity is easy on a tree, as described by my algorithm in the comments, undirected st-connectivity is not (directly) reducible to st-connectivity on a tree.
Therefore SL=L was not established until Reingold showed st-connectivity on an undirected graph is indeed solvable in log-space.
Given a directed graph $G$ of size $n$ and two vertices $s$ and $t$, first create a graph $G'$ by making $n$ copies of every vertex $u$ in $G$ as the new vertex $(u, i)$ in $G'$, where $i$ goes from $1$ to $n$ for the respective copies. Then, represent each edge $(u, v)$ in $G'$ by the transition $(u, i) \mapsto (v, i+1)$. Since any path from $s$ to $t$ is of length at most $n$, it then follows that a path from $s$ to $t$ exists in $G$ if and only if it exists in $G'$. Furthermore, since $i$ is always increasing in $(u, i)$, it is clear $G'$ is a DAG. Finally, the mapping can be computed in logarithmic space.
However, the approach does not work for undirected graphs, because cycles can occur in the layering technique. So although st-connectivity is easy on a tree, as described by my algorithm in the comments, undirected st-connectivity is not (directly) reducible to st-connectivity on a tree.
Therefore SL=L was not established until Reingold showed st-connectivity on an undirected graph is indeed solvable in log-space.
Context
StackExchange Computer Science Q#42451, answer score: 5
Revisions (0)
No revisions yet.