On the PLS-complexity of maximum constraint assignment

In this paper, we investigate the complexity of computing locally optimal solutions for the local search problem Maximum Constraint Assignment (MCA). For our investigation, we use the framework of PLS, as defined by Johnson et al. (1988) [9], . In a nutshell, the MCA-problem is a local search version of weighted, generalized MaxSat on constraints (functions mapping assignments to integers) over variables with higher valence; additional parameters in simultaneously limit the maximum length p of each constraint, the maximum appearance q of each variable and its valence r. We focus on hardness results and show PLS-completeness of (3,2,3)-MCA and (2,3,6)-MCA using tight reductions from Circuit/Flip. Our results are optimal in the sense that is solvable in polynomial time for every r∈N. We also pay special attention to the case of binary variables and show that is tight PLS-complete. For our results, we extend and refine a technique from Krentel (1989) [10].