3
$\begingroup$

Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim that independent set can also be solved in time polynomial in terms of $n$ and exponential in terms of $k$ ? ($k$ here stands for the minimum size of an independent set)

$\endgroup$
  • $\begingroup$ my intuition dictates that the answer is yes because vertex cover and independent set are essentially the same problem and the minimum set size and minimum vertices numbers are closely related. Can anyone confirm ? $\endgroup$ – 372 May 8 '13 at 23:41
4
$\begingroup$

No. The typical reduction from Independent Set to Vertex Cover doesn't preserve the parameter ($k$). A graph with a vertex cover of size $k$ has an independent set of size $n-k$, so we no longer have $n$ restricted to the polynomial part.

This separation is one of the basic conjectures of Parameterized Complexity. Parameterized Complexity is a bivariate complexity theory where problems are given with not only the normal input, but also a parameter. For example the (natural) parameterized version of Vertex Cover is:

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.

$\endgroup$
  • $\begingroup$ Thank you so much. The magnitude of your answer exceeded any expectations $\endgroup$ – 372 May 9 '13 at 1:31
  • $\begingroup$ @AdamPflepinsky, further references, if you're interested beyond this question, can be found on the (not that great) wikipedia page, but the big ones are three books: Downey & Fellows, "Parameterized Complexity" (the original monograph); Flum & Grohe, "Parameterized Complexity Theory" (newer and very comprehensive, somewhat dense at times); and Niedermeier, "Invitation to Fixed Parameter Algorithms" (a Habilitationschrift turned monograph, more focussed on FPT problems and algorithmic techniques, less complexity theory). $\endgroup$ – Luke Mathieson May 9 '13 at 4:14

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.