3
$\begingroup$

We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$ is the size of the independent set).

What about approximating it in FPT time?

Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

What about other $f(k)$s?

Improve this question
$\endgroup$
1
  • $\begingroup$ I believe this is the state of the art: arxiv.org/abs/1708.03515, and Section 1 gives a good overview of other known results. $\endgroup$
    – Alex Golovnev
    Commented Aug 19, 2017 at 3:36

1 Answer 1

Reset to default
1
$\begingroup$

In the paper: Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, the authors prove the following bound for Maximum Independent Set:

For any $r$ larger than some constant, any $r$-approximation algorithm for the maximum independent set problem must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ time. This nearly matches the upper bound of $2^{n/r}$.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Assuming ETH**. $\endgroup$
    – R B
    Commented Jul 9, 2017 at 20:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.