A randomized algorithm for long directed cycle

DOI10.1016/J.IPL.2016.02.005MaRDI QIDQ264199zbMATH OpenOpenAlexFDO

Authors Meirav Zehavi

Publication date 6 April 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08892

zbMATH Keywords

algorithms\(k\)-pathlong directed cycleparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Paths and cycles (05C38)

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^{\ast }(maxt(G,2k),4^{k+o(k)})$ (randomized time $O^{\ast }(maxt(G,2k),4^k)$). In particular, we get that {sc LDC} can be solved in randomized time $O^{\ast }(4^k)$.

Recommendations

• scientific article; zbMATH DE number 6469131
• Long directed \((s,t)\)-path: FPT algorithm
• Finding a long directed cycle
• Finding Long Paths, Cycles and Circuits
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time

Cites work

• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Color-coding
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Finding a long directed cycle
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Mixing Color Coding-Related Techniques
• Nonconstructive tools for proving polynomial-time decidability
• Parameterized algorithms
• Representative families: a unified tradeoff-based approach
• Representative sets of product families

Cited in

(4)

• scientific article; zbMATH DE number 7525484 (Why is no real title available?)
• scientific article; zbMATH DE number 6469131 (Why is no real title available?)
• Long directed \((s,t)\)-path: FPT algorithm
• Going far from degeneracy

This page was built for publication: A randomized algorithm for long directed cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q264199)