Local Max-Cut on Sparse Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916216087511040 |
|---|---|
| author | Schwartzman, Gregory |
| author_facet | Schwartzman, Gregory |
| contents | 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)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_00182 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Local Max-Cut on Sparse Graphs Schwartzman, Gregory Data Structures and Algorithms 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)}$. |
| title | Local Max-Cut on Sparse Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.00182 |