# Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

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.

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.

• 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? – John Smith Jun 28 '13 at 10:48
• Hint: Count the number of vertices in each connected component. – Yuval Filmus Jun 28 '13 at 15:54
• Another hint for those of us who didn't? :) – R S Jun 30 '14 at 10:50