7
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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