  We bound the smoothed running time of the FLIP algorithm for local Max-Cut as
a function of $\alpha$, the arboricity of the input graph. We show that, with
high probability and in expectation, the following holds (where $n$ is the
number of nodes and $\phi$ is the smoothing parameter):
  1) When $\alpha = O(\log^{1-\delta} n)$ FLIP terminates in $\phi poly(n)$
iterations, where $\delta \in (0,1]$ is an arbitrarily small constant. Previous
to our results the only graph families for which FLIP was known to achieve a
smoothed polynomial running time were complete graphs and graphs with
logarithmic maximum degree.
  2) For arbitrary values of $\alpha$ we get a running time of $\phi
n^{O(\frac{\alpha}{\log n} + \log \alpha)}$. This improves over the best known
running time for general graphs of $\phi n^{O(\sqrt{ \log n })}$ for $\alpha =
o(\log^{1.5} n)$. Specifically, when $\alpha = O(\log n)$ we get a
significantly faster running time of $\phi n^{O(\log \log n)}$.
