# Existence of W[1]-Hard construction from multiple hard problems

I am a research scholar working on parameterized complexity. Currently, I am exploring ways to prove the hardness of a problem by providing W[1]-Hard constructions. A problem is known to be fixed-parameter tractable w.r.t to a parameter $$p$$, if there exists an algorithm that runs in $$O(|V|^{O(1)} \cdot f(p))$$ time. A problem is known to be W[1]-Hard w.r.t a parameter $$p$$, if a parameterized reduction exists from an already known hard problem.
Consider a problem $$P$$ and there exists a W[1]-Hard construction from another hard problem $$A$$ to $$P$$. Since $$P$$ is W[1]-Hard, can I say that there must be a W[1]-Hard construction from any other hard problem $$B$$ to $$P$$? or it depends on how close $$B$$ is to $$P$$ as per the problem definition. Please give some clarity on this.
TIA

• Your definition of W[1]-hard is not correct. If you use the correct definition (W[1] is defined e.g. complexityzoo.net/Complexity_Zoo:W#w1. A is W[1]-hard if all problems in W[1] reduce to A, via a type of reduction as specified, e.g., in Downey & Fellows 2013 Ch. 20: link.springer.com/chapter/10.1007/978-1-4471-5559-1_20) the answer will be much clearer. Oct 4, 2022 at 5:06
• Yes, I was not thinking straight. I have updated what I actually meant on W[1]-Hard definition earlier. Oct 4, 2022 at 6:09
• When you say "a hard problem A" do you mean that A is W[1]-hard, or some other kind of "hardness"? And when you say "a W[1]-hard construction" do you mean a parametrized reduction? Oct 4, 2022 at 6:15
• As per the context, I meant W[1]-hard when I mentioned "hard problem A" and I meant parameterized reduction when I said "W[1]-hard construction". Oct 4, 2022 at 6:18
• Okay. This is a site for research-level questions, but your question seems to me more like a standard exercise in the definitions, in which case it would be more suitable for cs.stackexchange.com. Is there something more research-level in your question that I've missed? Oct 4, 2022 at 7:59