<p>No, this is impossible for your parameters.  With <span class="math-container">$s$</span> bits of space, you can only visit at most <span class="math-container">$2^s$</span> vertices of the graph.  Now set <span class="math-container">$s = O((\log k)^d)$</span> and <span class="math-container">$k=(\log n)^2$</span> and it is clear that you cannot visit all of the graph, as <span class="math-container">$2^s = o(n)$</span>.  Thus for any algorithm that uses only <span class="math-container">$O((\log k)^d)$</span> bits of space, there exist graphs where you fail to detect a <span class="math-container">$k$</span>-cycle (e.g., because the <span class="math-container">$k$</span>-cycle is in the unvisited part of the graph).</p>
<hr />
<p>If <span class="math-container">$k=n^{\Theta(1)}$</span>, 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 <span class="math-container">$v_0$</span> and store it (which requires <span class="math-container">$\log n = O(\log k)$</span> bits); then, non-deterministically guess a path of length <span class="math-container">$k$</span>, counting up to <span class="math-container">$k$</span> as you go (which requires <span class="math-container">$\log k$</span> bits), checking that none of the intermediate vertices are equal to <span class="math-container">$v_0$</span> and the final vertex is equal to <span class="math-container">$v_0$</span>.</p>
<p>If <span class="math-container">$k=n^{\Theta(1)}$</span>, 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.</p>

CC BY-SA 4.0
2021-05-25T06:32:10.037Z
(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$.
Emil Jeřábek
CC BY-SA 4.0
2021-05-25T09:06:21.093Z
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
Slugger
CC BY-SA 4.0
2021-05-25T01:56:00.823Z
2021-05-25T02:02:38.103Z
2021-05-25T02:02:38.103Z
D.W.
<p>For a graph <span class="math-container">$G$</span>, I want to test if it contains a cycle of length <span class="math-container">$k$</span>, for some <span class="math-container">$k$</span> much smaller than <span class="math-container">$|G|$</span>. 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 <span class="math-container">$k$</span>-clique.</p>
<p>I considered first a well known much simpler case, which is testing if <span class="math-container">$G$</span> is in fact a <span class="math-container">$k$</span> cycle. This can be done using <span class="math-container">$O(\log k)$</span> variables: Assume for simplicity for the moment that <span class="math-container">$k=4m$</span>. Such an algorithm then boils down to the fact that we can test if two vertices have distance <span class="math-container">$t$</span> in space complexity <span class="math-container">$O(\log t)$</span>. Then we test to see if there are four vertices <span class="math-container">$x_1,x_2,x_3,x_4$</span> such that <span class="math-container">$d(x_1,x_3)=d(x_2,x_4)=2m$</span> and all other distances between the <span class="math-container">$x_i$</span> are <span class="math-container">$m$</span>.</p>
<p>Note crucially that this algorithm will fail to report true if the graph <span class="math-container">$G$</span> has <span class="math-container">$k$</span> vertices and contains a cycle, but also some additional edges.</p>
<p>My question now is the following: Is there a similar (or completely different) algorithm that detects when a graph <span class="math-container">$G$</span> of potentially large size, contains a <span class="math-container">$k$</span> cycle that is not necessarily induced, that has <span class="math-container">$O((\log k)^d)$</span> space complexity for some fixed <span class="math-container">$d \geq  1$</span>? Clearly such an algorithm with space complexity <span class="math-container">$ k $</span> exists, but I would like to do better.</p>
<p>P.S. I don't know if it makes much of a difference, but in the applications I am looking at, <span class="math-container">$k$</span> will itself be of the order <span class="math-container">$(\log n)^2$</span> where <span class="math-container">$n = |G|$</span>.</p>
<p>P.P.S Also, the graph <span class="math-container">$G$</span> that I am looking at will be sparse, they are Erdos-Renyi random graphs in <span class="math-container">$\mathbb{G}(n,n^{-c})$</span> for some <span class="math-container">$c\in (0,1)$</span>.</p>

CC BY-SA 4.0
2021-05-25T01:59:39.497Z
Do you want to know if there exists a simple cycle of length $k$, or an arbitrary cycle (possibly repeating vertices)?
D.W.
CC BY-SA 4.0
2021-05-25T06:36:29.287Z
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)$.
Emil Jeřábek
<graph-theory><graph-algorithms><space-complexity>
Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$
Slugger
# Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$

(Asked by: username_0 on 2021-05-24)

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

**Tags:** graph-theory, graph-algorithms, space-complexity
> **Comments:**
> **username_1**: Do you want to know if there exists a simple cycle of length $k$, or an arbitrary cycle (possibly repeating vertices)?  
> **username_2**: 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)$.  

---

## 1 answers

### Answer by username_1 on 2021-05-25. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_2**: (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$.  
> **username_0**: 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  

---

