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?