# The complexity of checking for short cycles in a graph

In general, the problem of finding a Hamiltonian cycle is NP-complete (Karp 1972; Garey and Johnson 1983, p. 199).

Next, as for determining the existence of long cycles, I don't hold much hope for efficient algorithms. However, what about short cycles? For instance, 3-cycles, 4-cycles, and so on. For a $$k$$-cycle, at what value of $$k$$ does the algorithmic complexity transition from polynomial time to non-polynomial time? Is there a clear boundary?

• You can expect that the complexity be polynomial of a degree that grows with $k$. Though my opinion is not authoritative, I don't think that you will observe a transition.
– user16034
Aug 28, 2023 at 9:21
• I had posted an answer, but I’ve deleted it. $\Theta(n^k)$ would be for $k$-cliques, not $k$-cycles. Duh! Aug 29, 2023 at 2:42
• OK, @PålGD, I’ve restored it… with a mod. Aug 29, 2023 at 13:51

The problem of finding a simple $$k$$-cycle is FPT, which means that there exists an algorithm running in time $$O(f(k) \cdot n^{O(1)})$$.

Alon, Yuster, Zwick (Color coding, JACM 1995) give an algorithm for exact $$k$$-cycle in expected time $$O(k! \log k \cdot n^\omega)$$.

They also give an algorithm with worst case time $$2^{O(k)} nm$$ or $$2^{O(k)} n^\omega$$.

Fomin, Lokshtanov, Panolan, and Saurabh (JACM 2016) give a $$O(2.619^k n^{O(1)})$$ for finding a $$k$$-cycle.

As you can see, when $$k$$ approaches $$n$$, this looks more and more like an $$c^n$$ algorithm.

The best known randomized algorithm for detecting hamiltonicity is $$O(1.657^n)$$ by Björklund (SIAM J Computing, 2014), and to the best of my knowledge, the best algorithm for deterministic Hamiltonian Cycle is the $$O(2^n n^2)$$ algorithm by Bellman.

If your graph has $$n$$ vertices and you’re interested in $$k$$-cycles, then a brute-force inspection will look at each of the $$n \choose k$$ possible $$k$$-tuples. Thus, assuming that $$k$$ is small—in other words, that $$k = O(1)$$—that approach is $$\Theta(n^k)$$.