Faster deterministic parameterized algorithm for k-path

DOI10.1016/J.TCS.2019.04.024MaRDI QIDQ2272387zbMATH OpenOpenAlexWikidataFDO

Authors Dekel Tsur

Publication date 10 September 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithms\(k\)-pathparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Paths and cycles (05C38)

Abstract: In the k-Path problem, the input is a directed graph $G$ and an integer $kgeq1$, and the goal is to decide whether there is a simple directed path in $G$ with exactly $k$ vertices. We give a deterministic algorithm for k-Path with time complexity $O^{\ast }(2.554^k)$. This improves the previously best deterministic algorithm for this problem of Zehavi [ESA 2015] whose time complexity is $O^{\ast }(2.597^k)$. The technique used by our algorithm can also be used to obtain faster deterministic algorithms for k-Tree, r-Dimensional k-Matching, Graph Motif, and Partial Cover.

Recommendations

• Planar \(k\)-path in subexponential time and polynomial space
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Parameterized algorithm for 3-path vertex cover
• Narrow sieves for parameterized paths and packings

Cites work

• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Color-coding
• Divide-and-Color
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding detours is fixed-parameter tractable
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Long directed \((s,t)\)-path: FPT algorithm
• Mixing Color Coding-Related Techniques
• Narrow sieves for parameterized paths and packings
• On Linear Time Minor Tests with Depth-First Search
• Parameterized approximation algorithms for packing problems
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• Representative families: a unified tradeoff-based approach

Cited in

(16)

• The k-distinct language: parameterized automata constructions
• The \(k\)-distinct language: parameterized automata constructions
• Computing Pathwidth Faster Than 2 n
• Two edge-disjoint paths with length constraints
• On kernels for \(d\)-path vertex cover
• A note on algebraic techniques for subgraph detection
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• scientific article; zbMATH DE number 7525484 (Why is no real title available?)
• Detours in directed graphs
• A fast parameterized algorithm for co-path set
• QUBO formulations of the longest path problem
• Planar \(k\)-path in subexponential time and polynomial space
• Long directed \((s,t)\)-path: FPT algorithm
• Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
• Determinantal sieving
• Going far from degeneracy

This page was built for publication: Faster deterministic parameterized algorithm for \(k\)-path

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