# Constant value NP-complete vs W[1]-hard

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?

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!