Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

Stefan Kratsch, Daniel Marx, Magnus Wahlstrom

Research output: Contribution to journalArticlepeer-review

135 Downloads (Pure)

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 languageEnglish
Pages (from-to)1-28
Number of pages28
JournalACM Transactions on Computation Theory (TOCT)
Volume8
Issue number1
DOIs
Publication statusPublished - 3 Feb 2016

Cite this