2
$\begingroup$

Consider the following decision problems:

$CONN$= {$〈G,k〉$$G$ is undirected graph with at least $k$ connected components}
$E-CONN$= {$〈G,k〉$$G$ is undirected graph with exactly $k$ connected components}

I'd like to show this two problem are in $NL$. I Know it's possible to guess a vertex from each connected component and then verify the connectivity of the component (by guessing paths to other vertices). But how can I verify all guessed vertices are different, when it's impossible to hold $k$ vertices on the work tape?

$\endgroup$
  • $\begingroup$ Hint: Use NL = coNL. $\endgroup$ – dkaeae Jun 11 at 9:35
  • $\begingroup$ Hint: As you've observed, you cannot hold $k$ guesses at once. Instead, go through every vertex and maintain some counter. $\endgroup$ – sdcvvc Jun 11 at 9:39
4
$\begingroup$

We can assume without loss of generality that the vertex set is $1,\ldots,n$. Let us say that a vertex is minimal if it has the minimal value in its connected component. You can check that a vertex in minimal in NL by checking that it is not connected to any smaller vertex.

A graph has at least $k$ connected components iff there is a list $v_1 < v_2 < \cdots < v_k$ of minimal vertices. This shows that CONN is in NL. Since NL=coNL, it follows that E-CONN is also in NL.

Morale: if you want to make sure that you guessed $k$ distinct vertices, guess them in increasing order.


Since undirected connectivity is in L, we can actually count the number of connected components in L, by just going over all vertices, and counting how many of them are minimal.

$\endgroup$

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.