A randomized algorithm for long directed cycle

• We present a parameterized algorithm, LDC-Alg, for Long Directed Cycle.
• Currently, LDC-Alg is the fastest algorithm for Long Directed Cycle.
• LDC-Alg can use any algorithm for k-Path as a black box.

Given a directed graph G and a parameter k, the Long Directed Cycle (LDC) problem asks whether G contains a simple cycle on at least k vertices, while the k-Path problem asks whether G contains a simple path on exactly k vertices. Given a deterministic (randomized) algorithm for k-Path as a black box, which runs in time t(G,k)t(G,k), we prove that LDC can be solved in deterministic time O⁎(max⁡{t(G,2k),4k+o(k)})O⁎(max⁡{t(G,2k),4k+o(k)}) or in randomized time O⁎(max⁡{t(G,2k),4k})O⁎(max⁡{t(G,2k),4k}). In particular, we get that LDC can be solved in randomized time O⁎(4k)O⁎(4k).