EPTAS for Hard Graph Cut Problems for Dense Graphs

Kaisei Deguchi, Ken-ichi Kawarabayashi, Hiroaki Mori

Everywhere-$\hat{I}´$-dense graphs are defined as graphs on $n$ vertices in which every vertex has degree at least $\hat{I}´n$ for some constant $\hat{I}´>0$. Approximation schemes are vital for ha…