Asked By : 372
Answered By : Luke Mathieson
Vertex Cover
Input: A graph $G$, a positive integer $k$.
Parameter: $k$.
Question: Does $G$ have a vertex cover of size at most $k$?
So each parameterized problem has two (formally explicit) metrics: the size of the input $n$, and the parameter $k$. We then say that a problem $Pi$ is fixed-parameter tractable if there is an algorithm that decides each instance $(x,k)$ of $Pi$ in time bounded by $f(k)cdot|x|^{O(1)}$ for some computable function $f$ dependent only on $k$ (i.e. polynomial with constant degree in $|x| = n$, but essentially free in $k$). We call the class of all such problems $FPT$. So Vertex Cover is in $FPT$ when parameterized by the size of the vertex cover. The main intractability framework for Parameterized Complexity is called the $W$-hierarchy, a series of classes $W[t]$ where $W[i] subseteq W[i+1]$ and $FPT subseteq W[1]$. Although it’s split into lots of classes, the $W$-hierachy bears a practical relationship to $FPT$ in a similar manner to that of $NP$ to $P$, in that if a problem is $W[t]$-hard for some $t$, then it has no $FPT$ algorithm unless $W[t] = FPT$, and we conjecture that $FPT subset W[1]$ for similar reasons to $P subset NP$. Getting back to your question again, finally, it turns out that Independent Set is $W[1]$-complete when parameterized by the size of the independent set. That is, unless $W[1] = FPT$, Independent Set has no algorithm with running time bounded by $f(k)n^{O(1)}$ for any $f$, where $k$ is the size of the independent set. Additional Note: Of course we don’t have to parameterize by the size of the answer, we can use anything we feel like, the normal guidelines are that it should be something that can reasonably be expected to be small compared to the input size, and it should be able to vary independently of the input size. A common structural parameter for example is the treewidth of a graph. You can parameterize by measures relating to the size of the input, but then we have to introduce a bunch of different classes.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11904