<p>Arbitarily Weighted Planar Max Cut is polynomialy solvable. Shih, Wu, and Kuo provided a polynomial time algorithm with run-time of $O(n^{3/2} \log n)$.</p>

<p><a href="http://doi.ieeecomputersociety.org/10.1109/12.53581" rel="noreferrer">Unifying Maximum Cut and Minimum Cut of a Planar Graph</a>, IEEE Transactions on Computers, May 1990, vol. 39, no. 5, pp. 694-697</p>

CC BY-SA 2.5
2010-12-31T13:30:28.587Z
2010-12-31T13:30:28.587Z
Mohammad Al-Turkistany
<p>After reading the <a href="https://doi.org/10.1007/BF01068642" rel="nofollow noreferrer" title="Terebenkov, A.P. NP-completeness of maximum-cut and cycle-covering problems for a planar graph. Cybern Syst Anal 27, 16–20 (1991)">paper</a> you mentioned, it seems that the reduction stated in the paper is incomplete, therefore <strong>the result may not be correct</strong>.</p>
<p>In the paper the author gave a reduction from 3SAT to a problem called <em>planar max-cycle-covering</em> (although it is not consistent with the usual sense of a covering in graph theory, it is more like <em>max-edge-disjoint-cycles</em> problem), and proving that the max-cycle-covering problem and max-cut problem are dual to each other on planar graphs. While the second implication is correct, the reduction part mimics a proof to the NP-hardness of <a href="https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf" rel="nofollow noreferrer" title="Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976)">planar Hamiltonian cycle problem</a>, and there may be a flaw in it.</p>
<p>In that proof one need a gadget for <em>XOR-in-series</em> (See Fig. 3 in the <a href="https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf" rel="nofollow noreferrer" title="Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976)">Hamiltonian paper</a>); although the construction works in the Hamiltonian ones, I see no evidence that a similar construction is possible for cycle-covering, and there are no explanations in the paper. (And we need such a gadget in the NP-hardness proof of cycle-covering, see Fig. 6 in the <a href="https://doi.org/10.1007/BF01068642" rel="nofollow noreferrer" title="Terebenkov, A.P. NP-completeness of maximum-cut and cycle-covering problems for a planar graph. Cybern Syst Anal 27, 16–20 (1991)">max-cut paper</a>.) The main problem is that for Hamiltonian cycle we can always be sure that the middle edge C must be passed though, hence we can &quot;transfer&quot; the XOR by the presence of the middle edge; but in cycle-covering we cannot guarantee that edge C must be passed though unless it is within a cycle passing though a heavy-weighted edge, and this is not the case here. (In fact we cannot enforce the edge being passed though, since in Fig. 6 if an edge C is passed though then the corresponding literal in the clause is true.)</p>
<p>My guessing is that planar max-cycle-covering cannot simulate 3-fan-in OR function, which is required in 3SAT. Supported with the <a href="https://cstheory.stackexchange.com/questions/4037/what-is-the-complexity-status-of-arbitarily-weighted-planar-max-cut/4040#4040">answer</a> by <a href="https://cstheory.stackexchange.com/users/495/mohammad-al-turkistany">Mohammad Al-Turkistany</a>, one should believe that planar max-cut problem is polynomial time solvable.</p>

CC BY-SA 4.0
2011-01-01T15:23:45.933Z
2023-02-07T10:45:24.933Z
2023-02-07T10:45:24.933Z
Hsien-Chih Chang 張顯之
<p>If you search on the internet for the Complexity Status of Arbitarily Weighted Planar Max Cut you seem to get conflicting answers.</p>
<p>On one hand, there are references that Barahona solved this problem in the 1980's.</p>
<p>On the other there is this paper:
<a href="https://doi.org/10.1007/BF01068642" rel="nofollow noreferrer">NP-completeness of maximum-cut and cycle-covering problems for planar graphs</a></p>
<p>My question is what is the Complexity Status of Arbitarily Weighted Planar Max Cut?</p>

CC BY-SA 4.0
2022-06-22T22:26:36.213Z
Planar Max-Cut reduces to computing a min-cost T-join in the dual graph which in turn reduces to computing a min-cost perfect matching. This was first shown by Hadlock in 1975. The paper is available here. https://web.eecs.umich.edu/~pettie/matching/Hadlock-maxcut-planar-graph-reduction-to-T-join.pdf
Chandra Chekuri
CC BY-SA 4.0
2023-02-07T15:21:48.343Z
Would it be possible to add to the question a formal statement of what is this problem "Arbitarily Weighted Planar Max Cut"? searching for it on the Web only gives links to the question itself.
Antoine Amarilli 'a3nm'
<cc.complexity-theory><ds.algorithms>
What is the Complexity Status of Arbitarily Weighted Planar Max Cut?
Zelah 02
# What is the Complexity Status of Arbitarily Weighted Planar Max Cut?

(Asked by: username_0 on 2010-12-31)

If you search on the internet for the Complexity Status of Arbitarily Weighted Planar Max Cut you seem to get conflicting answers.

On one hand, there are references that Barahona solved this problem in the 1980's.

On the other there is this paper:
[NP-completeness of maximum-cut and cycle-covering problems for planar graphs](https://doi.org/10.1007/BF01068642)

My question is what is the Complexity Status of Arbitarily Weighted Planar Max Cut?

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: Planar Max-Cut reduces to computing a min-cost T-join in the dual graph which in turn reduces to computing a min-cost perfect matching. This was first shown by Hadlock in 1975. The paper is available here. https://web.eecs.umich.edu/~pettie/matching/Hadlock-maxcut-planar-graph-reduction-to-T-join.pdf  
> **username_2**: Would it be possible to add to the question a formal statement of what is this problem "Arbitarily Weighted Planar Max Cut"? searching for it on the Web only gives links to the question itself.  

---

## 2 answers

### Answer by username_4 on 2011-01-01. Score: 11 | Accepted answer

After reading the [paper](https://doi.org/10.1007/BF01068642 "Terebenkov, A.P. NP-completeness of maximum-cut and cycle-covering problems for a planar graph. Cybern Syst Anal 27, 16–20 (1991)") you mentioned, it seems that the reduction stated in the paper is incomplete, therefore **the result may not be correct**.

In the paper the author gave a reduction from 3SAT to a problem called *planar max-cycle-covering* (although it is not consistent with the usual sense of a covering in graph theory, it is more like *max-edge-disjoint-cycles* problem), and proving that the max-cycle-covering problem and max-cut problem are dual to each other on planar graphs. While the second implication is correct, the reduction part mimics a proof to the NP-hardness of [planar Hamiltonian cycle problem](https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf "Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976)"), and there may be a flaw in it.

In that proof one need a gadget for *XOR-in-series* (See Fig. 3 in the [Hamiltonian paper](https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf "Garey, M. R.; Johnson, D. S.; Tarjan, R. Endre. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976)")); although the construction works in the Hamiltonian ones, I see no evidence that a similar construction is possible for cycle-covering, and there are no explanations in the paper. (And we need such a gadget in the NP-hardness proof of cycle-covering, see Fig. 6 in the [max-cut paper](https://doi.org/10.1007/BF01068642 "Terebenkov, A.P. NP-completeness of maximum-cut and cycle-covering problems for a planar graph. Cybern Syst Anal 27, 16–20 (1991)").) The main problem is that for Hamiltonian cycle we can always be sure that the middle edge C must be passed though, hence we can "transfer" the XOR by the presence of the middle edge; but in cycle-covering we cannot guarantee that edge C must be passed though unless it is within a cycle passing though a heavy-weighted edge, and this is not the case here. (In fact we cannot enforce the edge being passed though, since in Fig. 6 if an edge C is passed though then the corresponding literal in the clause is true.)

My guessing is that planar max-cycle-covering cannot simulate 3-fan-in OR function, which is required in 3SAT. Supported with the [answer](https://cstheory.stackexchange.com/questions/4037/what-is-the-complexity-status-of-arbitarily-weighted-planar-max-cut/4040#4040) by [Mohammad Al-Turkistany](https://cstheory.stackexchange.com/users/495/mohammad-al-turkistany), one should believe that planar max-cut problem is polynomial time solvable.


---

### Answer by username_3 on 2010-12-31. Score: 7

Arbitarily Weighted Planar Max Cut is polynomialy solvable. Shih, Wu, and Kuo provided a polynomial time algorithm with run-time of $O(n^{3/2} \log n)$.

[Unifying Maximum Cut and Minimum Cut of a Planar Graph](http://doi.ieeecomputersociety.org/10.1109/12.53581), IEEE Transactions on Computers, May 1990, vol. 39, no. 5, pp. 694-697


---

