<p>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.</p>

<p>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 <a href="http://arxiv.org/abs/1104.4890" rel="nofollow">Łącki and Sankowski</a> (2011).  </p>

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

CC BY-SA 4.0
2020-09-27T17:09:39.880Z
What's the fastest open source solve in practice for Max Cut?
Royi
CC BY-SA 3.0
2013-12-13T04:29:18.953Z
2013-12-14T14:21:42.040Z
2013-12-14T14:21:42.040Z
Jeffε
<p>In 1990's, the paper <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.5518">Unifying Maximum Cut and Minimum Cut of a Planar Graph</a> described an
$O(n^{3/2}\log n)$-time algorithm for Weighted Planar Max Cut, a landmark in the field. </p>

<p>Recently, this paper appeared:</p>

<blockquote>
  <p>Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time 
  <a href="http://arxiv.org/abs/1003.1320">http://arxiv.org/abs/1003.1320</a></p>
</blockquote>

<p>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?</p>

<p>In general, have any improvements in Weighted Planar Max Cut been published?</p>

<time-complexity>
What is the fastest algorithm for Weighted Planar Max Cut
Zelah 02
# What is the fastest algorithm for Weighted Planar Max Cut

(Asked by: username_0 on 2013-12-11)

In 1990's, the paper [Unifying Maximum Cut and Minimum Cut of a Planar Graph](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.5518) 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?

**Tags:** time-complexity


---

## 1 answers

### Answer by username_1 on 2013-12-13. Score: 7

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](http://arxiv.org/abs/1104.4890) (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.

> **Comments:**
> **username_2**: What's the fastest open source solve in practice for Max Cut?  

---

