Counting strongly connected components in a directed graph in $NL$

Define $$K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least k strongly connected components} \}$$

I want to show that $$K\_SCC \in NSPACE(\log n)$$, using that $$st-CONN$$ and $$\overline{st-CONN}$$ are both in NL, where $$st-CONN = \{\langle G,s,t \rangle \,:\, \text{there is a path from s to t in G} \}$$.

Would appreciate any help

• Any strongly connected component $C$ is uniquely represented by the vertex $x\in C$ that has the smallest numerical label. Show that you can recognize such vertices in NL, and then you can just count them in increasing order. – Emil Jeřábek Jun 17 at 15:22

1 Answer

Ask the prover to give you any node from $$k$$ distinct connected components.

You have only to verify that the nodes are not in the same connected components (hence, they are in $$k$$ different components, meaning that $$\langle G, k\rangle \in K_{SCC}$$)

Also, ask for the proof of $$st-CON$$ between any two of them.

Notice that even though the proof is gigantic, at every point in time the verifier will need to only verify a small portion of the proof: only one $$st-CON$$ is being processed at a time, hence the verifier can be constructed in such a way that will require only $$O(\log(n))$$ space.

The pseudocode for the verifier should look similar to this:

• For every $$i\neq j$$ with $$1\le i,j\le k$$, do:
• Take a look at the next $$O(\log(n))$$ bits of proof, and verify $$st-CON$$ for the $$i$$'th and the $$j$$'th nodes
• As the question is stated, $k$ is not constant. It is part of the input. – Emil Jeřábek Jun 17 at 18:42
• Oops :p I totally missed this important thing... – nir shahar Jun 17 at 19:01
• When I think about it, since at every point in time the verifier only checks one $ST-con$ proof of size $O(\log(n))$, then the verifier can just check the proofs one by one in some predefined order, and the verifier wont use more than $O(\log(n))$ space. Yes, the proof is larger, but if I remember correctly thats allowed for as long as the verifier requires small space. – nir shahar Jun 17 at 19:15
• This is true except for how you specify which $k$ nodes you want to show are in different components. This will take $O(k\log(n))$ memory, which is not logarithmic in the size of $k$... – nir shahar Jun 17 at 19:23
• The definition of NL does not allow you to generate a polynomial-size “proof” and subsequently verify it in logarithmic space. This would in fact give you all of NP. See my comment below the question how to do this correctly. – Emil Jeřábek Jun 17 at 19:27