Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language.
Is there an equivalently defined class that can take $O(1)$ parameters? It may be useful for defining this for problems that are not driven by a single parameter. Unfortunately, there does not seem to be any material on extra parameters, including in the book Parameterized Complexity Theory.
Yes, it's exactly the same class. You can take any constant size list of parameters and combine them just using addition. This is particularly obvious in Flum and Grohe's formulation of $FPT$ where problems are equipped with a parameterization $\kappa : x \rightarrow \mathbb{N}$.
So for example, you can take a problem with two parameters $k$ and $r$, and produce a combined parameter $k+r$ (or indeed using any moderately sane function), as if the running time is bounded by some function $f(k,r)$ (we can ignore the $|x|^{O*(1)}$ part for the moment)), then it is bounded by the function $f(g(k+r),h(k+r)) = f'(k+r)$, where $g$ and $h$ do whatever is necessary to turn $k+r$ into a sufficiently usable form (in most cases, this is nothing).
Note that this produces the intuition you expect. If $(\Pi,\kappa) \in FPT$, then it is still in $FPT$ when you add a new parameter, however it is not necessarily true that if $(\Pi,\kappa_{1} + \kappa_{2}) \in FPT$ then either $(\Pi,\kappa_{1}) \in FPT$ or $(\Pi,\kappa_{2}) \in FPT$.
As an example, deleting $k$ vertices to obtain an $r$-regular graph is $W[1]$-hard with parameter $k$, $paraNP$-complete with parameter $r$ but in $FPT$ with parameter $k+r$.
