Problem
Local search alg (the single-flip alg) is a 2-approximation for the Max Cut problem. But in fact, that local search alg may not have polynomial run-time, which means it would not be a valid approximation alg after all (since approximation algs, though sub-optimal, need to at least be fast). Give an input instance of the max cut problem that demonstrates how/why the single-flip alg may have a run-time that is super-polynomial.