If you want to make money online : Register now

[Solved]: Multiple FPT Parameters

, , No Comments
Problem Detail: 

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.

Asked By : Ryan

Answered By : Luke Mathieson

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43377

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback