Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

摘要

For a finite set F of Boolean relations, Max Ones SAT(.T) and Exact Ones SAT(f) are generalized satisfiability problems where every constraint relation is from F, and the task is to find a satisfying assignment with at least/exactly k variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For Max Ones SAT(JH), we give a classification into 5 different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed k, and NP-hard already for k = 1. For Exact Ones SAT(r), we refine the classification obtained earlier by having a closer look at the fixed-parameter tractable cases and classifying the sets F for which Exact Ones SAT(F) admits a polynomial kernel.