4
$\begingroup$

The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states

A maximal cut of a cubic graph can be computed in polynomial time

Browsing through some other related results (for example this SODA paper) one gets the impression that this problem is actually NP complete even for cubic instances. In particular, the last paper states that this is indeed so if the graph is subcubic.

That makes me wonder.. What's going on? Is the survey paper (and the result cited therein) faulty or is there some point that I am missing?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

Maximal cut is different from maximum cut (MAX-CUT). In maximum cut, the goal is to find a cut cutting the maximal number of edges. In maximal cut, the goal is to find a local maximum: a cut such that switching the side of any single vertex does not result in more edges being cut. Such a cut exists, since the maximum cut is also maximal. But finding a maximum cut is apparently harder than finding just a maximal cut.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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