patternMinor
Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$
Viewed 0 times
connectivitynontextdirectreductionfrom
Problem
We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\text{-}connectivity$ is many-one log-space reducible to $st\text{-}connectivity$. But is there a direct/combinatorial reduction that doesn't go through the configuration graph of the Turing machines in $\mathsf{NL}$?
$\mathsf{stConnectivity}$ (a.k.a. $stPATH$):
Given directed graph $G$ and vertices $s$ and $t$,
Is there a directed path from vertex $s$ to vertex $t$?
Clarifications:
You can assume a graph is given by its adjacency matrix (however this is not essential since standard representations of graphs are log-space convertible to each other.)
It is possible to unpack the proof of $\mathsf{NL\text{-}hard}$ness of $st\text{-}connectivity$ and move it into the proof so the proof does not use it that theorem as a lemma. However this is still the same construction essentially. What I am looking for is not this, I want a conceptually direct reduction. Let me give an analogy with the $\mathsf{NP}$ case. We can reduce various $\mathsf{NP\text{-}complete}$ problems to each other by using the fact that they are in $\mathsf{NP}$ therefore reduce to $SAT$ and $SAT$ reduces to the other problem. And we can unpack and combine these two reductions to get a direct reduction. However it is often possible to give a conceptually much simpler reduction that doesn't go through this intermediate step (you can remove mentioning it, but it is still there conceptually). For example, to reduce $HamPath$ or $VertexCover$ or $3\text{-}Coloring$ to $SAT$ we don't say $HamPath$ is in $\mathsf{NP}$ and therefore reduces to $SA$ since $SAT$ is $\mathsf{NP\text{-}hard}$. We can give a simple intuitive formula that is satisfiable iff the graph has a Hamiltonian path.
Another example, we have reductions from other problems in $\mathsf{NL}$ to $st\text{-}Connectivity$ which do not rely on $\mat
$\mathsf{stConnectivity}$ (a.k.a. $stPATH$):
Given directed graph $G$ and vertices $s$ and $t$,
Is there a directed path from vertex $s$ to vertex $t$?
Clarifications:
You can assume a graph is given by its adjacency matrix (however this is not essential since standard representations of graphs are log-space convertible to each other.)
It is possible to unpack the proof of $\mathsf{NL\text{-}hard}$ness of $st\text{-}connectivity$ and move it into the proof so the proof does not use it that theorem as a lemma. However this is still the same construction essentially. What I am looking for is not this, I want a conceptually direct reduction. Let me give an analogy with the $\mathsf{NP}$ case. We can reduce various $\mathsf{NP\text{-}complete}$ problems to each other by using the fact that they are in $\mathsf{NP}$ therefore reduce to $SAT$ and $SAT$ reduces to the other problem. And we can unpack and combine these two reductions to get a direct reduction. However it is often possible to give a conceptually much simpler reduction that doesn't go through this intermediate step (you can remove mentioning it, but it is still there conceptually). For example, to reduce $HamPath$ or $VertexCover$ or $3\text{-}Coloring$ to $SAT$ we don't say $HamPath$ is in $\mathsf{NP}$ and therefore reduces to $SA$ since $SAT$ is $\mathsf{NP\text{-}hard}$. We can give a simple intuitive formula that is satisfiable iff the graph has a Hamiltonian path.
Another example, we have reductions from other problems in $\mathsf{NL}$ to $st\text{-}Connectivity$ which do not rely on $\mat
Solution
It is possible, if messy, to convert the proof of the Immerman-Szelepcsényi theorem to the reduction you want. There is absolutely no need to use the NL-completeness of st-connectivity.
Given an instance $G=(V,E),s,t$, we construct a new graph $G'=(V',E'),s',t'$. The "major vertices" of $V'$ record the following information: the current distance $d$ from $s$, the number of vertices of distance at most $d-1$, the number of vertices of distance $d-1$ counted so far, the current vertex we're guessing if it has distance at most $d-1$, the number of vertices of distance at most $d$ counted so far, the current vertex we're determining whether it has distance at most $d$. The minor vertices handle the part where we guess a path of length at most $d-1$ to a vertex which we guess to be of distance at most $d-1$. Edges that involve showing the vertex $t$ is reachable from $s$ are dropped. For each vertex which we're testing at the current distance, we only move forward to the next vertex if we have accounted for all vertices of smaller distance. When moving from distance $d$ to distance $d+1$, we copy the requisite information. The starting vertex $s'$ accounts for the fact that $s$ is the only vertex of distance zero. The ending vertex $t'$ is pointed at by all vertices representing the fact that the process has finished up to (and including) distance $n-1$, where $n=|V|$.
As you can see, it will be quite messy to write everything in full and correctly, but definitely possible. No overt use of NL-completeness was made, in that we never use the configuration graph of any NL machine. That's not needed, since we have something better than the configuration graph - the input instance itself.
Given an instance $G=(V,E),s,t$, we construct a new graph $G'=(V',E'),s',t'$. The "major vertices" of $V'$ record the following information: the current distance $d$ from $s$, the number of vertices of distance at most $d-1$, the number of vertices of distance $d-1$ counted so far, the current vertex we're guessing if it has distance at most $d-1$, the number of vertices of distance at most $d$ counted so far, the current vertex we're determining whether it has distance at most $d$. The minor vertices handle the part where we guess a path of length at most $d-1$ to a vertex which we guess to be of distance at most $d-1$. Edges that involve showing the vertex $t$ is reachable from $s$ are dropped. For each vertex which we're testing at the current distance, we only move forward to the next vertex if we have accounted for all vertices of smaller distance. When moving from distance $d$ to distance $d+1$, we copy the requisite information. The starting vertex $s'$ accounts for the fact that $s$ is the only vertex of distance zero. The ending vertex $t'$ is pointed at by all vertices representing the fact that the process has finished up to (and including) distance $n-1$, where $n=|V|$.
As you can see, it will be quite messy to write everything in full and correctly, but definitely possible. No overt use of NL-completeness was made, in that we never use the configuration graph of any NL machine. That's not needed, since we have something better than the configuration graph - the input instance itself.
Context
StackExchange Computer Science Q#1509, answer score: 4
Revisions (0)
No revisions yet.