4
$\begingroup$

I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly $10\sqrt{n}$ strongly connected components is in $NL$.

We saw in class that checking whether a directed graph contains exactly $C$ strongly connected components is in $NL$ for any fixed $C$, but I thought about this question the whole day and I absolutely have no idea how to do it in $NL$ when then number of SCC required is $10\sqrt{n}$. In the test this question was worth 20 points, so it shouldn't be too hard so I thought that maybe I am missing something important.

$\endgroup$
7
$\begingroup$

Hint: Suppose $C_1,\ldots,C_\ell$ are the connected components and $v_i$ is the minimal vertex in $C_i$. Suppose further that $v_1 < v_2 < \cdots < v_\ell$. Show how to certify the fact that this data is correct in NL by keeping at most two of these indices at a time.

Here are some more details for a slightly simpler problem: verifying whether an undirected graph contains exactly $10\sqrt{n}$ connected components. We keep a counter $k$ of vertices accounted for. Suppose the vertices are numbered $1$ to $n$, and for $t$ going from $1$ to $10\sqrt{n}$, do the following:

  1. Guess a vertex $v_t > v_{t-1}$ (where $v_0 = 0$).
  2. For all $v < v_t$, verify that $v$ is not connected to $v_t$.
  3. For each $v \geq v_t$, guess whether $v$ is connected to $v_t$ or not, and verify the guess; for each vertex connected to $v_t$, increase $k$.

If at the end $k = n$ then all vertices are accounted for, and the graph contains exactly $10\sqrt{n}$ connected components.

I leave the straightforward modification that solves the actual problem to the reader.

$\endgroup$
  • 1
    $\begingroup$ Hmm In order to verity that all $v_i$ are in different connected components I need to check that there is no path between any pair of two of them. I can check that there is no path between two vertices in NL, but given v_1,..,v_n in order to check that there is no path between any pair of them I need to keep many index (since in NL i can't go back when reading the certificate) What am I missing here? $\endgroup$ – John Smith Jun 28 '13 at 10:48
  • 1
    $\begingroup$ Hint: Count the number of vertices in each connected component. $\endgroup$ – Yuval Filmus Jun 28 '13 at 15:54
  • $\begingroup$ Another hint for those of us who didn't? :) $\endgroup$ – R S Jun 30 '14 at 10:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.