<p>Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA</p>
<ul>
<li>Ryan Williams, <a href="https://doi.org/10.1016/j.tcs.2005.09.023" rel="nofollow noreferrer">A new algorithm for optimal <span class="math-container">$2$</span>-constraint satisfaction and its implications</a>, Theoretical Computer Science, Volume 348, Issues 2–3, 8 December 2005.</li>
</ul>

CC BY-SA 4.0
2021-08-21T07:54:41.220Z
What does TIA stand for?
Rodrigo de Azevedo
CC BY-SA 4.0
2021-08-21T21:53:10.087Z
@RodrigodeAzevedo Probably “thanks in advance”.
Emil Jeřábek
CC BY-SA 4.0
2021-08-21T22:30:00.353Z
I'm not sure why someone downvoted this; I think it's a good question. As far as I know, the answer is "yes." We sort of used $2^{\omega n/3}$ being optimal for solving MAX-CUT as a hardness assumption in work from a few years ago.
Huck Bennett
CC BY-SA 4.0
2021-08-24T19:37:40.630Z
Yes, this is still the best known algorithm for the Max-CUT problem on graphs of unbounded average degree. For graphs of small average degree (say, <=10 or so), faster algorithms exist.
Alex Golovnev
CC BY-SA 4.0
2021-08-26T10:00:39.300Z
@AlexGolovnev, do you mind sharing the faster algorithm?
Omar Shehab
CC BY-SA 4.0
2021-08-26T14:43:05.090Z
@OmarShehab, here're two examples, but I'm not sure if these are the best known algorithms for Max-CUT in sparse graphs: https://www.sciencedirect.com/science/article/pii/S0167637706000587    and   https://golovnev.org/papers/max2sat.pdf
Alex Golovnev
<graph-theory><graph-algorithms><semidefinite-programming><max-cut><network-modeling>
Fastest exact algorithm for MAXCUT
Omar Shehab
# Fastest exact algorithm for MAXCUT

(Asked by: username_0 on 2021-08-20)

Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA

* Ryan Williams, [A new algorithm for optimal $2$-constraint satisfaction and its implications](https://doi.org/10.1016/j.tcs.2005.09.023), Theoretical Computer Science, Volume 348, Issues 2–3, 8 December 2005.

**Tags:** graph-theory, graph-algorithms, semidefinite-programming, max-cut, network-modeling

> **Comments:**
> **username_1**: What does TIA stand for?  
> **username_2**: @RodrigodeAzevedo Probably “thanks in advance”.  
> **username_3**: I'm not sure why someone downvoted this; I think it's a good question. As far as I know, the answer is "yes." We sort of used $2^{\omega n/3}$ being optimal for solving MAX-CUT as a hardness assumption in work from a few years ago.  
> **username_4**: Yes, this is still the best known algorithm for the Max-CUT problem on graphs of unbounded average degree. For graphs of small average degree (say, <=10 or so), faster algorithms exist.  
> **username_0**: @AlexGolovnev, do you mind sharing the faster algorithm?  
> **username_4**: @OmarShehab, here're two examples, but I'm not sure if these are the best known algorithms for Max-CUT in sparse graphs: https://www.sciencedirect.com/science/article/pii/S0167637706000587    and   https://golovnev.org/papers/max2sat.pdf  

---

## 0 answers

