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

Question

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?

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!