Skip to main content
Computer Science

Return to Question

edited title
Link
Balchandar Reddy
Balchandar Reddy
  • 182
  • 8

No parameterised reduction for thea problem indicates FPT or not?

Elaborated the question
Source Link
Balchandar Reddy
Balchandar Reddy
  • 182
  • 8

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 recently 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?

I am currently working on parameterized complexity, especially on the hard proofs. There is a problem $P$ and a parameter $x$, I recently 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 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?

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?

Source Link
Balchandar Reddy
Balchandar Reddy
  • 182
  • 8

No parameterised reduction for the problem indicates FPT or not?

I am currently working on parameterized complexity, especially on the hard proofs. There is a problem $P$ and a parameter $x$, I recently 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 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?