2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What makes you think $s,t$ connectivity for trees can be solved in L? Also - Linear time is in a RAM model. In a TM it would require at least $\Omega(n\log n)$, otherwise it would be regular. $\endgroup$ – Shaull May 12 '15 at 4:58
  • $\begingroup$ Perhaps you can see a flaw in my algorithm: keep track of the current node $u$ and the most recently visited node $r$. When a vertex $u$ is reached, take the edge that points to the next lexicographical neighbor after $r$. If $u$ has no neighbors, go back to $r$. Since you only ever visit a node $v$ for a second time from the same way you left $v$ (because the graph has no cycles), it follows that you will explore all neighbors of $v$. Since this will happen for every node in the graph, after traversing each edge twice you will have visited $t$ if a path from $s$ to $t$ exists. $\endgroup$ – Bryce Sandlund May 12 '15 at 5:08
  • $\begingroup$ But you'll need to keep a lexicographical counter for each node along the path you are currently exploring. That is not logarithmic. $\endgroup$ – Shaull May 12 '15 at 5:21
  • $\begingroup$ The graph must be described by bits, and so each vertex has some bit representation. Since the space complexity of the input doesn't count, you keep this as your way to determine the lexicographically next neighbor. Note you are not modifying the input tape. $\endgroup$ – Bryce Sandlund May 12 '15 at 5:23
  • $\begingroup$ Or perhaps you meant you need the counter for each vertex in the path... This is not needed, because you always return to a vertex from the same edge you left it. Thus it suffices to just keep track of the most recently visited vertex, and this will always be the lexicographical counter of current vertex $u$. $\endgroup$ – Bryce Sandlund May 12 '15 at 5:37
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ In other words, if you regard an undirected graph as a directed graph where all edges occur in opposite pairs $u \leftrightarrow v$, the reduction will not give back an undirected graph. $\endgroup$ – sdcvvc May 12 '15 at 22:06
  • 1
    $\begingroup$ I don't understand how your reduction can work for directed graphs but not undirected graphs. If the reduction works for all directed graphs, shouldn't it work for the digraph you get from any undirected graph by replacing each undirected edge with a bidirectional edge? $\endgroup$ – David Richerby May 13 '15 at 8:40
  • $\begingroup$ You could do that, but the reduction requires making the edges in the layering technique directed. If they're bidirectional, then the layering technique does not get you anywhere if the original graph contained a cycle. $\endgroup$ – Bryce Sandlund May 14 '15 at 1:33
  • 1
    $\begingroup$ I still don't understand why it doesn't work for undirected graphs. The same conclusions still hold: if there is a path from $s$ to $t$ in $G$, then there exists a path from $(s,1)$ to $(t,i)$ in $G'$ (for some $i$). (Why? If $t$ is reachable from $s$ in $G$, it's reachable in at most $n$ steps. The existence of cycles doesn't change this.) $G'$ is still a DAG. So you can still reduce s-t connectivity in an undirected graph to st-connectivity on a DAG. Right? So why do you say it doesn't work on an undirected graph? (Cc: @DavidRicherby) $\endgroup$ – D.W. May 14 '15 at 5:47
  • 1
    $\begingroup$ Oh, yeah, you can reduce st-connectivity on an undirected graph to st-connectivity on a DAG, but you cannot reduce st-connectivity on an undirected graph to st-connectivity on a tree. $\endgroup$ – Bryce Sandlund May 15 '15 at 18:52

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.