The parameterized complexity of k‐flip local search for SAT and MAX SAT

SAT and MAX SAT are among the most prominent problems for which local search algorithms have been successfully applied. A fundamental task for such an algorithm is to increase the number of clauses satisfied by a given truth assignment by flipping the truth values of at most $k$ variables ( $k$ ‐flip local search). For a total number of $n$ variables the size of the search space is of order $n^k$ and grows quickly in $k$ ; hence most practical algorithms use 1‐flip local search only. In this paper we investigate the worst‐case complexity of $k$ ‐flip local search, considering $k$ as a parameter: is it possible to search significantly faster than the trivial $n^k$ bound? In addition to the unbounded case we consider instances with a bounded number of literals per clause and instances where each variable occurs in a bounded number of clauses. We also consider the related problem that asks whether we can satisfy all clauses by flipping the truth values of at most $k$ variables.