Question

Recall that a directed graph is strongly connectedif every two nodes are connected by a directed path in each direction. Let STRONGLY-CONNECTED= {(G)| G is a strongly connected graph}. Show that STRONGLY-CONNECTEDis NL-complete.

Short answer

It is clear that STRONGLY-CONNECTEDis NL-complete.

Step-by-step solution

Step-1:  STRONGLY−CONNECTED∈NL

First it has to show that$\mathbf{STRONGLY}\mathbf{-}\mathbf{CONNECTED}\mathbf{\in }\mathbf{NL}$ . Consider the machine that makes the following decision$\stackrel{\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}\mathbf{\_}}{\mathbf{STRONGLY}\mathbf{-}\mathbf{CONNECTED}}$.

On input (G),

1. Choose two nodes a and b in a nondeterministic manner.
2. Execute$\mathbf{PATH}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}$ . Accept if it rejects because the graph is not highly linked. Otherwise, you should reject it $\mathbf{STRONGLY}\mathbf{-}\mathbf{CONNECTED}\mathbf{\in }\mathbf{NL}$. because keeping the node numbers a and b only takes log space and PATH only takes log space. Finally, because $\mathbf{NL}\mathbf{=}\mathbf{CoNL}$, $\mathbf{STRONGLY}\mathbf{-}\mathbf{CONNECTED}\mathbf{\in }\mathbf{NL}$is the result.

Step-2: STRONGLY-CONNECTED is NL-Complete

It must then show that every other language in L can be reduced to STRONGLY-CONNECTED in log space. This is accomplished by setting PATH to STRONGLYCONNECTED. Consider the reduction below.

“On input (G, s, t)

1. Copy the entire file G to the output tape..
2. Furthermore, for each node i in G,
3. Output an edge from i to s.
4. Output an edge from t to i.

If a path exists from s to t, the resulting graph is truly strongly connected, because every node may now reach every other node via the s-t path. Because the only additional edges in the produced graph go into s and out of t, there can't be any new methods to travel from s to t if there is not a path from s to t, the constructed graph is not tightly connected.

Finally, we must confirm that a log space transducer can truly do the reduction. Indeed, despite the fact that the output has a size of $\mathrm{O}\left(\mathrm{n}\right)$, the only space required to accomplish the reduction is that which was previously utilised to keep a record of the node number i in the for loop.

Thus, from the above discussion it is clear that STRONGLY-CONNECTEDis NL-complete.