Local search is one of the most successful approaches for solving hard optimization problems. In local search, a set of neighbor solutions is assigned to every solution and one asks for a local optimum, i.e., a solution that has no better neighbor. To encapsulate the complexity of finding local optima, Johnson et al. (JCSS,1988) introduced the complexity class PLS. Shortly afterwards, Schäffer et al. (JOC,1991) showed PLS-completeness for several local search problems including LocalMax-Cut on graphs with unbounded degree with a FLIP-neighborhood in which one node changes the partition. Moreover, they showed two further results for LocalMax-Cut: First, there is an infinite family of instances and solutions for which every sequence of improving steps that ends up in a local optimum has exponential length (all-exp property). Second, the StandardAlgorithmProblem (SAP), i.e., the problem of finding a local optimum that is reachable from a given pair of an instance and initial solution via improving steps, is PSPACE-complete. On the positive side, Poljak (JOC,1995) showed that there are at most quadratically many improving steps possible for LocalMax-Cut on cubic graphs. This thesis provides three complexity results for LocalMax-Cut. First, it has the all-exp property if restricted to graphs with maximum degree four. Second, the SAP is PSPACE-complete for graphs with maximum degree four. Third, finding a local optimum is PLS-complete for graphs with maximum degree five.