In 1990's, the paper Unifying Maximum Cut and Minimum Cut of a Planar Graph described an $O(n^{3/2}\log n)$-time algorithm for Weighted Planar Max Cut, a landmark in the field.

Recently, this paper appeared:

Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time http://arxiv.org/abs/1003.1320

I was wondering if the time for Weighted Planar Max Cut could be improved from $O(n^{3/2}\log n)$ to $O(n \log^c n)$ for some small constant $c$, using ideas from this paper?

In general, have any improvements in Weighted Planar Max Cut been published?


1 Answer 1


Shih, Wu, and Kuo's "unifying" paper reduces the planar maximum cut problem to two related problems in planar graphs: (1) maximum-weight bipartite matching and (2) minimum cycle (aka weighed girth). Both problems are solved in $O(n^{3/2}\log n)$ time using divide-and-conquer algorithms that rely on Lipton and Tarjan's planar separator theorem.

After a long series of improvements, the minimum-weight cycle in a weighted planar graph can now be computed in $O(n \log\log n)$ time using a recent algorithm of Łącki and Sankowski (2011).

However, I am unaware of any improvement on the time to find maximum-weight matchings, which means Shih, Wu, and Kuo's $O(n^{3/2}\log n)$ time algorithm is still the fastest algorithm known (at least to me) for weighted planar max-cut.

  • $\begingroup$ What's the fastest open source solve in practice for Max Cut? $\endgroup$
    – Royi
    Sep 27, 2020 at 17:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.