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.

  • 2
    $\begingroup$ 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. $\endgroup$ Oct 4, 2022 at 5:06
  • $\begingroup$ Yes, I was not thinking straight. I have updated what I actually meant on W[1]-Hard definition earlier. $\endgroup$ Oct 4, 2022 at 6:09
  • $\begingroup$ 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? $\endgroup$ Oct 4, 2022 at 6:15
  • $\begingroup$ 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". $\endgroup$ Oct 4, 2022 at 6:18
  • $\begingroup$ 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? $\endgroup$ Oct 4, 2022 at 7:59


Your Answer

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