3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user16034
    Aug 28, 2023 at 9:21
  • 1
    $\begingroup$ I had posted an answer, but I’ve deleted it. $\Theta(n^k)$ would be for $k$-cliques, not $k$-cycles. Duh! $\endgroup$ Aug 29, 2023 at 2:42
  • 1
    $\begingroup$ OK, @PålGD, I’ve restored it… with a mod. $\endgroup$ Aug 29, 2023 at 13:51

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
0
5
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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