Chapter 8: Q34P (page 360)

Define CYCLE= {(G)| G is a directed graph that contains a directed cycle}. Show that CYCLEis NL-complete.

Short Answer

Expert verified

The implementation in log space is straightforward. Furthermore, a simple experiment demonstrates that $C Y C L E \in N L$ . As a result, CYCLE is NL-complete

Step by step solution

To Complete NL class

NL-complete is a complexity class in computational complexity theory that includes all languages that are complete for NL, a class of decision problems that can be handled by a nondeterministic Turing machine with a logarithmic amount of memory space.

To CYCLE is NL-complete

PATH should be reduced to CYCLE. The reduction is done by adding an edge from t to s in G to the PATH problem instance $(G, s, t)$ .

A directed cycle will occur in the modified G if a path from s to t exists in G. Other cycles, on the other hand, could exist in the modified G if they are already present in G.

To solve this issue, first remove all cycles from G. A levelled directed graph is one in which nodes are separated into groups called levels, $A_{1}, A_{2}, . . ., A_{k}$ , and only edges from one level to next higher level are allowed. A levelled graph is acyclic.

As the following reduction from the unconstrained PATH problem indicates, the PATH issue for levelled graphs is still NL-complete. Produce the levelled graph G’, whose levels are m copies of G's nodes, given a graph G with 2 nodes s and t and m total nodes.

If G contains an edge from i to j, draw an edge from node i at each level to node j at the next level.

Draw an edge from node I in one level to node I in the following level in each level. Let s0 represent the first-level node s, and t’ represent the last-level node t.

A path from s to t is shown in Graph G. A path from s’ to t’ can be found in G’. Then, add an edge from t’ to s’ in G’, then get a reduction from PATH to CYCLE. The reduction is straightforward in terms of computation, and its.