0
$\begingroup$

This question already has an answer here:

I want to know whether there is a relation between parameterized algorithms and approximation algorithms.

Like there will exist a fpt problem for problem P iff it have some f-approx algorithm.

I would be also happy if some one can give me reference.

Edit: It's just observation from my aspect that c-approx algo have fpt algo where c is constant. I am not able to prove it but I want contradicting example.

Also this implies there is a relation between kernel and the approximation algo.

$\endgroup$

marked as duplicate by D.W. Jul 20 '16 at 23:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ What research have you done? $\endgroup$ – Raphael Apr 5 '16 at 15:43
  • $\begingroup$ I think I have proof in one direction, I.e, fpt implies c-aprrox algo. we will find the a k kernal for problem P then use this as approx algo solution. Now we can traverse k=1 to n for optimal parameter. $\endgroup$ – Thinking Apr 6 '16 at 10:14
  • $\begingroup$ How does the size bound translate into a quality bound? $\endgroup$ – Raphael Apr 6 '16 at 11:22
  • 1
    $\begingroup$ yeah, this works for linear kernel only did not notice earliar. $\endgroup$ – Thinking Apr 6 '16 at 12:45