<p>In the paper: <a href="https://arxiv.org/abs/1308.2617" rel="nofollow noreferrer">Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses</a>, the authors prove the following bound for Maximum Independent Set:</p>

<blockquote>
  <p>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}$.</p>
</blockquote>

CC BY-SA 3.0
2017-07-09T20:01:19.763Z
Assuming ETH**.
R B
CC BY-SA 3.0
2017-07-09T17:03:41.800Z
2017-07-09T17:03:41.800Z
PsySp
<p>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).</p>

<p>What about approximating it in FPT time?</p>

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

<p>What about other $f(k)$s?</p>

CC BY-SA 3.0
2017-08-19T03:36:32.463Z
I believe this is the state of the art: https://arxiv.org/abs/1708.03515, and Section 1 gives a good overview of other known results.
Alex Golovnev
<ds.algorithms><approximation-algorithms><fixed-parameter-tractable><exp-time-algorithms>
Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?
JFK
# Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

(Asked by: username_0 on 2017-07-09)

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?

**Tags:** ds.algorithms, approximation-algorithms, fixed-parameter-tractable, exp-time-algorithms
> **Comments:**
> **username_1**: I believe this is the state of the art: https://arxiv.org/abs/1708.03515, and Section 1 gives a good overview of other known results.  

---

## 1 answers

### Answer by username_2 on 2017-07-09. Score: 1

In the paper: [Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses](https://arxiv.org/abs/1308.2617), 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}$.

> **Comments:**
> **username_3**: Assuming ETH**.  

---

