I am a research scholar currently working in parameterized algorithms. I am studying the complexity of a problem (say $P$) for $\Delta_{10}$ graphs and was able to provide a reduction from a known NP-complete problem. Hence, i have that $P$ is NP-complete on $\Delta_{10}$ graphs. It is obvious that there is no FPT (fixed-parameter tractable) algorithm for the problem w.r.t. the parameter maximum degree. My question is, can I say that since the problem is NP-complete for constant maximum degree graphs, it is also W[1]-hard for the parameter maximum degree?


1 Answer 1


By definition, a parametrized reduction from a parametrized problem $A$ to $B$ needs to satisfy the following properties:

  1. The reduction maps each instance $(x,k)$ of $A$ is mapped to some instance $(x',k')$ of $B$ such that $(x,k)$ is true if and only if $(x',k')$ is true.
  2. The parameter $k'$ obtained after the reduction needs to be bounded by a function of $k$.
  3. The reduction takes at most $f(k)\cdot|x|^{O(1)}$ time, for some computable function $f$.

A polynomial time reduction from $A'$ to $B'$ already satisfies property 1 and 3 if we add an arbitrary parameter to these problems. If we add a parameter $p$ to $B'$ such that $p\leq C$ on all instances for some constant $C$, then property 2 is also satisfied. So, there is a parametrized reduction from $A'$ with any parameter to $B'$ with a "bounded parameter".

Now take an NP-hard problem $X$ and a parameter $p$ that is bounded by a constant on all instances of $X$. There is a polynomial time reduction from CLIQUE to $X$, because $X$ is NP-hard and CLIQUE is in NP. By the argument above, there is a parametrized reduction from $k$-CLIQUE to $X$, so $X$ is W[1]-hard.

Now, to answer your question, yes, problems that are NP-hard become W[1]-hard if you add a parameter that is bounded by a constant on all inputs. However, the fact that your problem "$P$ for $\Delta_{10}$ graphs" becomes W[1]-hard after adding a bounded parameter is not a insightful property of your particular problem, precisely because this is true for any NP-hard problem.

In fact, a way to interpret the fact that some problem is W[1]-hard for some parameter is that we expect the additional assumption that this parameter is small will not help us to construct a polynomial time algorithm. If the parameter chosen is already guaranteed to be small in the problem, then assuming it is small a second time does not help!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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