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

作者：Szeider Stefan^*

来源：Discrete Optimization, 2011, 8(1): 139-145.

DOI：10.1016/j.disopt.2010.07.003

• Parameterized complexity
• Local search
• Maximum satisfiability

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.

• 出版日期2011-2