5
$\begingroup$

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 http://www.springerlink.com/content/xj7238374871347j/

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

$\endgroup$
7
$\begingroup$

After reading the paper 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, 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); 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.) 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 by @turkistany, one should believe that planar max-cut problem is polynomial time solvable.

$\endgroup$
6
$\begingroup$

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, IEEE Transactions on Computers, May 1990, vol. 39, no. 5, pp. 694-697

$\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.