Return to Answer

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.

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 Mohammad Al-Turkistany, one should believe that planar max-cut problem is polynomial time solvable.

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.

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.

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 arbitrary 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.

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.