A Randomized Algorithm for Long Directed Cycle

2015/10/29 by Zehavi, Meirav
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1510.08892

Abstract

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

Related

• Hitting Long Directed Cycles is Fixed-Parameter Tractable
• Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
• Faster deterministic parameterized algorithm for k-Path
• On r-Simple k-Path
• Approximating Long Cycle Above Dirac's Guarantee