Approximation Algorithms for Finding Maximum Induced Expanders

Shayan Oveis Gharan, Alireza Rezaei

We initiate the study of approximating the largest induced expander in a given graph $G$. Given a $\Delta$-regular graph $G$ with $n$ vertices, the goal is to find the set with the larg…