# Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$

For a graph $$G$$, I want to test if it contains a cycle of length $$k$$, for some $$k$$ much smaller than $$|G|$$. I am interested in particular in an algorithm with low space complexity. The cycle need not be induced, so that I want to return success also for instance in the case that G contains a $$k$$-clique.

I considered first a well known much simpler case, which is testing if $$G$$ is in fact a $$k$$ cycle. This can be done using $$O(\log k)$$ variables: Assume for simplicity for the moment that $$k=4m$$. Such an algorithm then boils down to the fact that we can test if two vertices have distance $$t$$ in space complexity $$O(\log t)$$. Then we test to see if there are four vertices $$x_1,x_2,x_3,x_4$$ such that $$d(x_1,x_3)=d(x_2,x_4)=2m$$ and all other distances between the $$x_i$$ are $$m$$.

Note crucially that this algorithm will fail to report true if the graph $$G$$ has $$k$$ vertices and contains a cycle, but also some additional edges.

My question now is the following: Is there a similar (or completely different) algorithm that detects when a graph $$G$$ of potentially large size, contains a $$k$$ cycle that is not necessarily induced, that has $$O((\log k)^d)$$ space complexity for some fixed $$d \geq 1$$? Clearly such an algorithm with space complexity $$k$$ exists, but I would like to do better.

P.S. I don't know if it makes much of a difference, but in the applications I am looking at, $$k$$ will itself be of the order $$(\log n)^2$$ where $$n = |G|$$.

P.P.S Also, the graph $$G$$ that I am looking at will be sparse, they are Erdos-Renyi random graphs in $$\mathbb{G}(n,n^{-c})$$ for some $$c\in (0,1)$$.

• Do you want to know if there exists a simple cycle of length $k$, or an arbitrary cycle (possibly repeating vertices)?
– D.W.
May 25, 2021 at 1:59
• No, you cannot test if two vertices have distance $t$ in space $O(\log t)$; you can only do it in space $O(\log n)$ (assuming wlog $t\le n$). In particular, if $t$ is constant, you cannot test this in constant space; you need space $\Theta(\log n)$. May 25, 2021 at 6:36

No, this is impossible for your parameters. With $$s$$ bits of space, you can only visit at most $$2^s$$ vertices of the graph. Now set $$s = O((\log k)^d)$$ and $$k=(\log n)^2$$ and it is clear that you cannot visit all of the graph, as $$2^s = o(n)$$. Thus for any algorithm that uses only $$O((\log k)^d)$$ bits of space, there exist graphs where you fail to detect a $$k$$-cycle (e.g., because the $$k$$-cycle is in the unvisited part of the graph).

If $$k=n^{\Theta(1)}$$, and if your definition of a cycle allows repeated vertices to appear in the cycle, then an algorithm exists. A simple approach is to guess a starting vertex $$v_0$$ and store it (which requires $$\log n = O(\log k)$$ bits); then, non-deterministically guess a path of length $$k$$, counting up to $$k$$ as you go (which requires $$\log k$$ bits), checking that none of the intermediate vertices are equal to $$v_0$$ and the final vertex is equal to $$v_0$$.

If $$k=n^{\Theta(1)}$$, and if your definition of a cycle does not allow repeated vertices to appear in the cycle, then I don't know whether an algorithm exists or not.

• (1) Without assumptions on $k$ and $n$, you algorithm works in space $O(\log n+\log k)$. (2) You formulated the algorithm as nondeterministic. But since the graph is undirected, you can make it run in deterministic space $O(\log n+\log k)$ using SL = L: perhaps a more direct reduction to USTCON is to consider a layered graph with $k+1$ copies $G_0,\dots,G_k$ where the original edges of $G$ now go between each pair of neighbouring copies, and then check the reachability of $v_0\in G_k$ from $v_0\in G_0$. May 25, 2021 at 6:32
• Thanks for this answer! I guess to summarize: any algorithm that potentially needs to visit all vertices of a graph will need at least space complexity $O(\log n)$ to even differentiate between nodes right? Makes sense May 25, 2021 at 9:06