Local Max-Cut on Sparse Graphs

We bound the smoothed running time of the FLIP algorithm for local Max-Cut as a function of $α$, 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 $φ$ is the smoothing parameter): 1) When $α= O(\log^{1-δ} n)$ FLIP terminates in $φpoly(n)$ iterations, where $δ\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 $α$ we get a running time of $φn^{O(\fracα{\log n} + \log α)}$. This improves over the best known running time for general graphs of $φn^{O(\sqrt{ \log n })}$ for $α= o(\log^{1.5} n)$. Specifically, when $α= O(\log n)$ we get a significantly faster running time of $φn^{O(\log \log n)}$.