Faster deterministic parameterized algorithm for k-Path

2018/08/13 by Tsur, Dekel · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1808.04185

Abstract

In the k-Path problem, the input is a directed graph G and an integer k≥ 1, 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^*(2.554^k). This improves the previously best deterministic algorithm for this problem of Zehavi [ESA 2015] whose time complexity is O^*(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.

Cited by

• Weighted k-Path and Other Problems in Almost O^*(2^k) Deterministic Time via Dynamic Representative Sets

Related

• Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)
• On r-Simple k-Path
• A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
• Faster Detours in Undirected Graphs
• Parameterized Complexity of Path Set Packing