EPTAS for Hard Graph Cut Problems for Dense Graphs

Kaisei Deguchi, Ken-ichi Kawarabayashi, Hiroaki Mori

Everywhere-$\delta$-dense graphs are defined as graphs on $n$ vertices in which every vertex has degree at least $\delta n$ for some constant $\delta >0$. Approximation schemes are vital for handl…