Is this a Fixed Parameter Tractable algorithm?

Question

Suppose my algorithm runs in time $O(nL^2)$, where $n$ is the size of the input, and $L$ some other parameter, which can get arbitrarily large w.r.t. $n$. My algorithm does not run in polynomial time, since $L$ can get arbitrarily large w.r.t. $n$. So I'd like to categorize it elsewise. Fixed Parameter Tractable algorithms, with regards to some defined parameter $k$, run in time $O(f(k)\times n^{O(1)})$, where $f$ is any function.

Would it be correct to state that my algorithm is Fixed Parameter Tractable (FPT) with regards to the parameter $L$?

Answer 1

If you consider $L$ to be a parameter, then yes, you have an FPT time algorithm, and your parameterized problem is indeed in the complexity class FPT, but be precise when you define your problem so that it is indeed stated as a parameterized problem.

Although we often refer to things as FPT algorithms, it is actually the problems that are FPT or not. Just as we don't have "NP-complete algorithms", we don't really have algorithms that are "FPT".

However, keep in mind that your algorithm also runs in pseduo-polynomial time in $O(n \cdot L^2)$ (if I understand $L$ correctly). So, since your might not be (weakly) NP-hard, I would state it as a pseudo-polynomial time algotithm.

(Definition). Your algorithm is pseudo-polynomial in $n$ and $L$ since it has running time $O(n \cdot L^2)$ and $L$ is an integer.

Ps: I claim that it is incorrect to say that we have an FPT algorithm, when it is the problem that belongs to FPT, and the algorithm runs in "FPT time". Of course, I call algorithms "FPT algorithms", too, but when it comes to the way we speak with students, I feel that it is important to make a distinction between problems and algorithms.

Answer 2

First and foremost, I would advise having another look at the basic definitions. An FPT instance is identified by a string $x$ and an integer $k$ such that $(x, k)$ is a yes-instance.

Put briefly, if $f(k)$ is not polynomial in terms of $n$ and still depends on $n$, then you cannot obtain an FPT algorithm. We require that $k$ is fixed, or independent of $n$, and thus $f(k)$ is always independent of $n$. However, if $f(k) = n^{O(1)}$, then our FPT algorithm is in fact a polynomial time algorithm. Hence, if $f(k) = O(2^n)$, the answer is definitely no.

Answer 3

Yes, it is technically correct to call such an algorithm FPT but rather pointless.

Suppose that the problem at hand is computable, say, it can be solved in time $T(n)$.

You write that $L$ is bounded from below by $\Omega(\sqrt{n})$.

Putting these two facts together, we have that the problem can be solved in time $T(c L^2)$ for some constant $c$. Taking $f(k)=T(c k^2)$, this is an FPT running time, since $T(c L^2)=f(L)\times n^0=f(L)\times n^{O(1)}$.

If a parameter $k$ is bounded in any way from below by any function of $n$ (no matter how slow growing), then the problem (assuming it is computable) is automatically fixed-parameter tractable in that parameter. We don't even need the "$n^{O(1)}$-part" of the running time, we can simply solve the problem in $f(k)$ time by computing an upper bound on $n$ from $k$ and then running a brute-force algorithm.