# Fastest exact algorithm for MAXCUT

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

• What does TIA stand for? Aug 21 '21 at 7:54
• @RodrigodeAzevedo Probably “thanks in advance”. Aug 21 '21 at 21:53
• 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. Aug 21 '21 at 22:30
• 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. Aug 24 '21 at 19:37
• @OmarShehab, here're two examples, but I'm not sure if these are the best known algorithms for Max-CUT in sparse graphs: sciencedirect.com/science/article/pii/S0167637706000587 and golovnev.org/papers/max2sat.pdf Aug 26 '21 at 14:43