2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 5 '20 at 22:38
  • $\begingroup$ @YuvalFilmus I've updated the question to contain the correct definition of reduction relative to this context. $\endgroup$ – Walker Panuccio Nov 5 '20 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.