Prof. Meirav Zehavi

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), we prove that LDC can be solved in deterministic time ^O∗(max{t(G,2k),^4k+o(k)}) or in randomized time ^O(maxi{t(G,2k),^4k}). In particular, we get that LDC can be solved in randomized time ^O(^4k).