2
$\begingroup$

$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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy