Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916843179999232 |
|---|---|
| author | Ahn, Jungho DeHaan, Ian Kim, Eun Jung Lee, Euiwoong |
| author_facet | Ahn, Jungho DeHaan, Ian Kim, Eun Jung Lee, Euiwoong |
| contents | We present a polynomial-time $(α_{GW} + \varepsilon)$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $α_{GW} \approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\varepsilon > 10^{-34}$ is a fixed constant. To attain this, we give an improved analysis of a slight modification of the Goemans-Williamson algorithm for graphs in which triangles can be packed into a constant fraction of their edges. We then pair this analysis with structural results showing that both interval graphs and split graphs either have such a triangle packing or have maximum cut close to their number of edges. We also show that, subject to the Small Set Expansion Hypothesis, there exists a constant $c > 0$ such that there is no polyomial-time $(1 - c)$-approximation for Maximum Cut on split graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10436 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson Ahn, Jungho DeHaan, Ian Kim, Eun Jung Lee, Euiwoong Data Structures and Algorithms F.2.2 We present a polynomial-time $(α_{GW} + \varepsilon)$-approximation algorithm for the Maximum Cut problem on interval graphs and split graphs, where $α_{GW} \approx 0.878$ is the approximation guarantee of the Goemans-Williamson algorithm and $\varepsilon > 10^{-34}$ is a fixed constant. To attain this, we give an improved analysis of a slight modification of the Goemans-Williamson algorithm for graphs in which triangles can be packed into a constant fraction of their edges. We then pair this analysis with structural results showing that both interval graphs and split graphs either have such a triangle packing or have maximum cut close to their number of edges. We also show that, subject to the Small Set Expansion Hypothesis, there exists a constant $c > 0$ such that there is no polyomial-time $(1 - c)$-approximation for Maximum Cut on split graphs. |
| title | Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2507.10436 |