Abstract
For a finite set Γ of Boolean relations, Max Ones SAT(Γ) and Exact Ones SAT(Γ) are generalized satisfiability problems where every constraint relation is from Γ, 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(Γ), we give a classification into five 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(Γ), we refine the classification obtained earlier by taking a closer look at the fixed-parameter tractable cases and classifying the sets Γ for which Exact Ones SAT(Γ) admits a polynomial kernel.
Original language | English |
---|---|
Pages (from-to) | 1-28 |
Number of pages | 28 |
Journal | ACM Transactions on Computation Theory (TOCT) |
Volume | 8 |
Issue number | 1 |
DOIs | |
Publication status | Published - 3 Feb 2016 |