Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

Édouard Bonnet

For every $\epsilon >0$, it is NP-hard to $n^{1-\epsilon }$-approximate Max Independent Set in $n$-vertex graphs [Hastad '96, Zuckerman '07]. In triangle-free graphs, a simpl…