| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427038 | Information Processing Letters | 2016 | 4 Pages |
•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).
