A randomized algorithm for long directed cycle

DOI10.1016/J.IPL.2016.02.005zbMATH Open1356.68264arXiv1510.08892OpenAlexW2964052962MaRDI QIDQ264199FDOQ264199

Meirav Zehavi

Publication date: 6 April 2016

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

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

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

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

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)

Cites Work

• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• Mixing Color Coding-Related Techniques
• Nonconstructive tools for proving polynomial-time decidability
• Title not available (Why is that?)
• Color-coding
• Finding a long directed cycle
• Parameterized Algorithms
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time

Cited In (5)

• On the complexity of finding internally vertex-disjoint long directed paths
• Going Far from Degeneracy
• Title not available (Why is that?)
• Title not available (Why is that?)
• Long directed \((s,t)\)-path: FPT algorithm

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)