I am currently working on parameterized complexity, especially on the hard proofs. There is a problem that I am currently working on, denoted by $P$ and a parameter $x$, I discovered that there is no parameterized reduction for $P$ w.r.t the parameter $x$ from any W-class. I have tried to give a reduction from a W[2]-hard, Dominating set problem parameterized by the solution size but got to know that due to the problem definition of $P$ and the structure of the parameter $x$, it is not possible. In fact, the reduction from any W-class is not likely to exist. My question is: What does this indicate? Does it mean the problem is fixed-parameter tractable (FPT) or something else?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Proving that there is no such reduction would only establish that the problem is not $W[2]$-hard. But that just means that the problem is not complicated in one particular fashion, it doesn't mean that the problem is easy. There are problems that are not $W[1]$-hard but are far, far from being FPT.
However, it would really surprise me if a somewhat natural problem is neither FPT nor $W[1]$-hard.
So given what you know about your problem, I'd expect the problem to be FPT; and you probably should try and prove that next.
-
$\begingroup$ Since, i have a proof that there does not exist a parameterized reduction from any $W$-class to $P$, doesnt this serve the purpose of proving that the problem is in FPT? $\endgroup$ Commented Mar 15, 2023 at 8:14
-
$\begingroup$ @BalchandarReddy No. As I explicitly state in my answer, being "not $\mathrm{W}[1]$-hard" doesn't imply anything at all about the problem being easy. The problem could even be noncomputable in the parameter. $\endgroup$– ArnoCommented Mar 15, 2023 at 10:56
-
$\begingroup$ I was able to prove that there won't be a parameterized reduction from any W[i]-class to the problem $P$. Doesnt this imply FPT? $\endgroup$ Commented Mar 16, 2023 at 7:39
-
$\begingroup$ @BalchandarReddy Why do you keep asking the same question over and over? $\endgroup$– ArnoCommented Mar 16, 2023 at 8:04
-
$\begingroup$ I think i misunderstood in some way, could you please let me know in which class the problem might fall other than in FPT? probably some figure might help in understanding better. TIA. $\endgroup$ Commented Mar 16, 2023 at 8:15