# What is the fastest algorithm to solve $k$-path problem?

$$k$$-Path problem

The problem: Given a graph $$G$$ with $$n$$ vertices and $$m$$ edges, does there exist a path of length $$k$$ in the graph?

The trivial algorithm to solve is in $$O^*(n^k)$$ time using dynamic programming. ($$^*$$ hides the polynomial factor.)

Question: What is the fastest algorithm for the $$k$$-Path problem?

## 1 Answer

For FPT algorithms (ignoring the polynomial factors), there is a $$2.851^k \cdot n^{O(1)}$$ deterministic algorithm and a $$1.66^k \cdot n^{O(1)}$$ randomized algorithm.

See Table of FPT races for references.