Local Max-Cut on Sparse Graphs

Abstract

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 $\varphi$ is the smoothing parameter): 1) When $\alpha =O({\log }^{1-\delta }n)$ FLIP terminates in $\varphi 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 $\varphi n^{O(\frac{\alpha }{\log n}+\log \alpha )}$. This improves over the best known running time for general graphs of $\varphi 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 $\varphi n^{O(\log \log n)}$.