Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

Getting Started

Consider a parameterized problem $F$. We use $n$ to denote the input size and $k$ to denote the parameter. Consider the fixed levels of $F$ which we denote by $\{F_k\}_{k\in\mathbb{N}}$.

Definitions

We say that $F$ is in non-uniform $FPT$ if there exists a constant $c$, a function $f(k)$, and a family of algorithms $\{A_k\}_{k\in\mathbb{N}}$ such that for every $k$, $A_k$ solves $F_k$ in $O(f(k) * n^c)$ time.

We say that $F$ is in uniform $FPT$ if there exists a constant $c$ and a function $f(k)$ such that there exists a parameterized algorithm that solves $F$ in $O(f(k) * n^c)$ time.

Remark: One could construct unnatural examples of paramterized problems that are in non-uniform $FPT$, but are not in uniform $FPT$. For example, take an undecidable language and define the parameter $k$ to be the input length.

Question

Does there exist a natural parameterized problem $F$ that is proven to be non-uniform $FPT$ and suspected (yet not proven) to be uniform $FPT$?

A More High-level Question

Does uniform vs non-uniform parameterized complexity have any relationship to uniform vs non-uniform circuit complexity?

Asked by user14207 (4,900 )
Sep 17, 2017 at 07:24