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

Question

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)$.

Answer 1

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.