Learning-augmented Maximum Independent Set
<|reference_start|>Learning-augmented Maximum Independent Set: We study the Maximum Independent Set (MIS) problem on general graphs within the framework of learning-augmented algorithms. The MIS problem is known to be NP-hard and is also NP-hard to approximate to within a factor of $n^{1-\delta}$ for any $\delta>0$. We show that we can break this barrier in the presence of an oracle obtained through predictions from a machine learning model that answers vertex membership queries for a fixed MIS with probability $1/2+\varepsilon$. In the first setting we consider, the oracle can be queried once per vertex to know if a vertex belongs to a fixed MIS, and the oracle returns the correct answer with probability $1/2 + \varepsilon$. Under this setting, we show an algorithm that obtains an $\tilde{O}(\sqrt{\Delta}/\varepsilon)$-approximation in $O(m)$ time where $\Delta$ is the maximum degree of the graph. In the second setting, we allow multiple queries to the oracle for a vertex, each of which is correct with probability $1/2 + \varepsilon$. For this setting, we show an $O(1)$-approximation algorithm using $O(n/\varepsilon^2)$ total queries and $\tilde{O}(m)$ runtime.<|reference_end|>
@article{braverman2024learning-augmented,
    title={Learning-augmented Maximum Independent Set},
    author={Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, Chen Wang},
    journal={arXiv preprint arXiv:2407.11364},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.11364},
    primaryClass={cs.DS cs.LG}
}