3
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Do you want to know if there exists a simple cycle of length $k$, or an arbitrary cycle (possibly repeating vertices)? $\endgroup$ – D.W. May 25 at 1:59
  • $\begingroup$ 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)$. $\endgroup$ – Emil Jeřábek May 25 at 6:36
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ (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$. $\endgroup$ – Emil Jeřábek May 25 at 6:32
  • $\begingroup$ 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 $\endgroup$ – Slugger May 25 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.