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

CC BY-SA 4.0
2022-10-04T05:06:33.167Z
Your definition of W[1]-hard is not correct. If you use the correct definition (W[1] is defined e.g. https://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: https://link.springer.com/chapter/10.1007/978-1-4471-5559-1_20) the answer will be much clearer.
Joshua Grochow
CC BY-SA 4.0
2022-10-04T06:09:25.933Z
Yes, I was not thinking straight. I have updated what I actually meant on W[1]-Hard definition earlier.
Balchandar Reddy
CC BY-SA 4.0
2022-10-04T06:15:42.970Z
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?
Joshua Grochow
CC BY-SA 4.0
2022-10-04T06:18:35.003Z
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".
Balchandar Reddy
CC BY-SA 4.0
2022-10-04T07:59:25.113Z
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?
Joshua Grochow
<np-hardness><reductions><parameterized-complexity>
Existence of W[1]-Hard construction from multiple hard problems
Balchandar Reddy
# Existence of W[1]-Hard construction from multiple hard problems

(Asked by: username_0 on 2022-10-04)

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

**Tags:** np-hardness, reductions, parameterized-complexity
> **Comments:**
> **username_1**: Your definition of W[1]-hard is not correct. If you use the correct definition (W[1] is defined e.g. https://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: https://link.springer.com/chapter/10.1007/978-1-4471-5559-1_20) the answer will be much clearer.  
> **username_0**: Yes, I was not thinking straight. I have updated what I actually meant on W[1]-Hard definition earlier.  
> **username_1**: 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?  
> **username_0**: 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".  
> **username_1**: 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?  

---

## 0 answers

