patternMinor
Acyclic Graph in NL
Viewed 0 times
graphacyclicstackoverflow
Problem
From the book The Nature of Computation by Moore and Mertens, exercise 8.9:
Consider the problem ACYCLIC GRAPH of telling whether a directed graph is acyclic. Show that the problem is in NL, and then show that the problem is NL-complete.
I am mainly interested in the first part. It's quite easy to show that it's in coNL (just guess a walk, vertex by vertex, from a vertex $v$ that returns to $v$), and then we can use the Immerman-Szelepcsényi Theorem to prove that it's in NL.
But I was not able to construct a Turing machine directly, i.e. a machine that shows that the problem is in NL without the help of Immerman-Szelepcsényi or the construction from their proof. My question thus is:
How can I show directly that ACYCLIC GRAPH is in NL?
Consider the problem ACYCLIC GRAPH of telling whether a directed graph is acyclic. Show that the problem is in NL, and then show that the problem is NL-complete.
I am mainly interested in the first part. It's quite easy to show that it's in coNL (just guess a walk, vertex by vertex, from a vertex $v$ that returns to $v$), and then we can use the Immerman-Szelepcsényi Theorem to prove that it's in NL.
But I was not able to construct a Turing machine directly, i.e. a machine that shows that the problem is in NL without the help of Immerman-Szelepcsényi or the construction from their proof. My question thus is:
How can I show directly that ACYCLIC GRAPH is in NL?
Solution
It's easy to see that the problem is coNL-complete.
If you could find a direct proof that ACYCLIC GRAPH is in NL, then it would be a direct proof of NL=coNL. However, as far as I know, nobody knows about a proof of this fact that does not use the inductive counting technique. See https://cstheory.stackexchange.com/questions/2145/alternate-proofs-of-immerman-szelepcsenyi-theorem and Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$.
(By the way, I find it bit easier to think about the problem "CYCLIC GRAPH" as in "graph that has a cycle"; it's easy to show that's it's NL-complete.)
If you could find a direct proof that ACYCLIC GRAPH is in NL, then it would be a direct proof of NL=coNL. However, as far as I know, nobody knows about a proof of this fact that does not use the inductive counting technique. See https://cstheory.stackexchange.com/questions/2145/alternate-proofs-of-immerman-szelepcsenyi-theorem and Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$.
(By the way, I find it bit easier to think about the problem "CYCLIC GRAPH" as in "graph that has a cycle"; it's easy to show that's it's NL-complete.)
Context
StackExchange Computer Science Q#32296, answer score: 3
Revisions (0)
No revisions yet.