How does to prove that language $$\textbf{X} = \{G \mid\text{ all connected connected components in $G$ are trees}\} \in \textbf{L}\,?$$ I know how to prove that language of undirected trees is in $\textbf{L}$ but I don't know what to do next.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Do you know of Reingold's algorithm? $\endgroup$– user12859Commented Jan 19, 2018 at 21:11
-
$\begingroup$ Yes, but Reingold's algorithm solves PATH problem for undirected G using O(logn) space memory and if I use this algorithm to find paths between s and all vertices (it gives connected component) I will need to store these vertices and for example I will give you a connected Graph ( only one connected component) you will need in O(n) memory. $\endgroup$– Jason GradlinCommented Jan 20, 2018 at 3:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Using Reingold's algorithm, you can count the number of connected components in a graph. For example, you can count the number of vertices which have the minimal index in their connected component (assuming some arbitrary ordering of the vertices), that is, the number of vertices $i$ that are not connected to any $j < i$.
Now use the following criterion: A graph contains a cycle iff there is an edge whose removal does not increase the number of connected components.
answered Jan 20, 2018 at 16:15
-
$\begingroup$ May you give me your contacts? $\endgroup$ Commented Jan 21, 2018 at 8:45