3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. I saw their $FPT$ definition (with $\kappa$ as a function instead of an integer) after I posted, and was originally thinking of it as an integer. $\endgroup$ – Ryan Jun 8 '15 at 2:50
  • 1
    $\begingroup$ @Ryan in a sense, the point of using a function is that you can just think of it as an integer. If you go back and look at the original definition, you could use anything as a parameter, and the "turning it into a number" part was handled in the running time, whereas Flum and Grohe formalised it into the definition. (Imagine parameterizing by a graph. It makes perfect sense after a while, but it's not the most natural way to start) $\endgroup$ – Luke Mathieson Jun 8 '15 at 2:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.