Settling the Complexity of Local Max-Cut (Almost) Completely

We consider the problem of finding a local optimum for the

Max-Cut

problem with FLIP-neighborhood, in which exactly one node changes the partition. Schäffer and Yannakakis (SICOMP, 1991) showed

$\mathcal{PLS}$

-completeness of this problem on graphs with unbounded degree. On the other side, Poljak (SICOMP, 1995) showed that in cubic graphs every FLIP local search takes

O

(

n

2

) steps, where

n

is the number of nodes. Due to the huge gap between degree three and unbounded degree, Ackermann, Röglin, and Vöcking (JACM, 2008) asked for the smallest

d

such that on graphs with maximum degree

d

the local

Max-Cut

problem with FLIP-neighborhood is

$\mathcal{PLS}$

-complete. In this paper, we prove that the computation of a local optimum on graphs with maximum degree five is

$\mathcal{PLS}$

-complete. Thus, we solve the problem posed by Ackermann et al. almost completely by showing that

d

is either four or five (unless

$\mathcal{PLS}$

⊆

$\mathcal{P}$

).

On the other side, we also prove that on graphs with degree

O

(log

n

) every FLIP local search has probably polynomial smoothed complexity. Roughly speaking, for any instance, in which the edge weights are perturbated by a (Gaussian) random noise with variance

σ

2

, every FLIP local search terminates in time polynomial in

n

and

σ

− 1

, with probability 1 − 

n

− Ω(1)

. Putting both results together, we may conclude that although local

Max-Cut

is likely to be hard on graphs with bounded degree, it can be solved in polynomial time for slightly perturbated instances with high probability.