# Proving that DCONN is NL-Complete

I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed.

Problem definitions:

RCH: Given a directed graph G and nodes x, y , is there a path from x to y?

DCONN: given a directed graph G, is it connected?

To my understanding we have have to prove two things:

1. $$DCONN \leq RCH$$
2. $$RCH \leq DCONN$$

Reduction $$\leq$$ in this case is defined as: $$L$$ is logspace-reducible to $$L^{'}$$ ($$L \leq_{log} L{'})$$ iff there is a LOGSPACE function f such that: $$x \in L$$ iff $$f(x) \in L{'}$$.

To be honest I have no idea where to even start. The following is my naive attempt to tackle the first issue. For the first part I thought that running $$n^2$$ RCH questions to see if node $$y$$ is reachable from node $$x$$ for all $$x,y \in G, x \neq y$$ will be sufficient to prove that $$G$$ is connected or not. But I am not sure if that is sufficient to be considered a reduction.

When it comes to the second part I have no idea where to even start. Any help or pointers would be appreciated.

• I am not sure if that is sufficient to be considered a reduction. If you don't know the notion of reductions in this case, you cannot expect to be able to prove that a reduction exists. Before attempting the exercise, make sure that you know the formal definition of reduction which is relevant here. – Yuval Filmus Nov 5 '20 at 22:38
• @YuvalFilmus I've updated the question to contain the correct definition of reduction relative to this context. – Walker Panuccio Nov 5 '20 at 23:11