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

  • 3
    $\begingroup$ What does TIA stand for? $\endgroup$ Aug 21, 2021 at 7:54
  • 3
    $\begingroup$ @RodrigodeAzevedo Probably “thanks in advance”. $\endgroup$ Aug 21, 2021 at 21:53
  • 4
    $\begingroup$ 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. $\endgroup$ Aug 21, 2021 at 22:30
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 24, 2021 at 19:37
  • 3
    $\begingroup$ @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 $\endgroup$ Aug 26, 2021 at 14:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.