Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

Abstract

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 simple argument gives a polynomial-time $n^{1/2}$-approximation algorithm, whereas, for every $\epsilon >0$, an $n^{1/4-\epsilon }$-approximation algorithm would imply that NP $\subseteq$ BPP [Bonnet, Thomassé, Tran, Watrigant; ESA '20]. In this note, we close this gap by proving the corresponding hardness against $n^{1/2-\epsilon }$-approximation algorithms. The reduction is very simple and uses the Moser-Tardos resampling algorithm to make the constructed graphs triangle-free. The soundness uses a result of Haeupler, Saha, and Srinivasan building on the proof of Moser and Tardos, to upper-bound the probability that a fixed relatively large subset is an independent set after the Moser-Tardos algorithm terminates. We generalize this scheme and show that, for any nonempty finite family $\mathcal{F}$ of graphs, each containing at least one cycle, for any $\epsilon >0$, an $n^{\mu (\mathcal{F})-\epsilon }$-approximation algorithm for Max Independent Set in graphs excluding every member of $\mathcal{F}$ as a subgraph implies that NP $\subseteq$ BPP, where $\mu (\mathcal{F}):=1-\underset{H\in \mathcal{F}}{\max }\underset{U\subseteq V(H),H[U]\text{contains a cycle}}{\min }(|U|-2)/(|E(H[U])|-1)$.

11 pages, 1 figure