Justifying that ISOLATED problem belongs to SPACE(log n)

Question

There is this problem in my Algorithm theory course for getting ready for exam and I just can't wrap my head around this

The problem ISOLATED: given a graph $G$ verify that there is a vertex $v$ for which there is no edge $uv$ that connects it to any other vertex $u$.

Justify that ISOLATED$\in$SPACE($log n$) where n is the number of vertices in the graph $G$

I have tough time thinking about space complexity as I am used to thinking about time complexity which I would say is $O(n^2)$

Answer 1

Recall the Undirected Graph Connectivity Problem.

• Instance: An undirected graph $G(V, E)$, and vertices $u, v \in V(G)$.
• Decision: Is there a $u-v$ path in $G$?

This problem is $\textsf{L}$-complete. Can you use this fact to design an algorithm using logspace?

Note that each vertex is represented using a binary string of length $\lceil \log_{2} |V| \rceil$.