Max cut in cubic graphs

Question

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?

Answer 1

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.