Somewhere in 2015, I encountered a nice algorithmic question during an interview for an algotreading company. The question was how one can decide if there is a cycle in an undirected connected graph? There are two immediate answers here, the first is running Breadth First Search (BFS) on arbitrary node and memorizing the nodes that were already visited. The search ends either when the algorithm complete scanning the whole graph or when it reaches some node twice, outputting “No” or “Yes” respectively. Another possible solution is by running Depth First Search (DFS) and keeping a variable to count the length of the longest path explored. The algorithm declare a cycle if at any point in time the length of the path reaches the number of vertices in the graph. For the rest of this post, denote that number by $n$ .

We will start from solving a slightly different problem then uses its solution as a procedure in our cycle-detection algorithm.

From here the algorithm is straightforward: denote the algorithm by $Alg\left(u,v;2^{k}\right)$ that upon receiving $u,v$ from the graph $G=\left(V,E\right)$ and $k\in\mathbb{N}$ :

The solution for s-t connectivity can be achieved by outputting “Yes” if and only if $Alg\left(s,t,2^{\lceil\log n\rceil}\right)=1$ .

How solving the s-t connectivity problem helps us with cycles detection? The next observation answer that: let $G=\left(V,E\right)$ be the graph in question and $u,v\in V$ two endpoints of some edge, they must stay connected after removing that edge from $G$ if and only if both participating in a cycle contained in $G$ .

Actually, for undirected graphs there is an algorithm with $\mathcal{O}\left(\log n\right)$ bits, improving the square on the log in the construction from previous section. The curious reader can read more about it here. For the directed case it is an open question whether we can improve the $\log^{2}n$ or not.

The directed s-t connectivity problem is an important theoretical problem because it captures the “hardness” of any problem that requires logarithmic amount of memory space. The reduction to show that is actually very easy, suppose we have an algorithm that solves some problem in $\mathcal{O}\left(s\right)$ space where $s$ is logarithmic in $n$ (and $n$ is the size of the input), generate the following directed graph: create a vertex $v$ for any state (memory configuration) of the algorithm. Since its memory is $\mathcal{O}\left(s\right)$ , there are at most $2^{\mathcal{O}\left(s\right)}=\mathcal{O}\left(poly\left(n\right)\right)$ states (thus vertices). Create an edge from $u$ to $v$ iff $v$ is a valid possible successor state of $u$ . Add a vertex $t$ and connects to it all the states that leads to outputting “Yes”. Denote by $s$ the starting-state of the algorithm and now solving the original problem is equivalent to finding a directed path from $s$ to $t$ in the states-graph.