Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. / Kratsch, Stefan; Marx, Daniel; Wahlstrom, Magnus.

In: ACM Transactions on Computation Theory (TOCT), Vol. 8, No. 1, 03.02.2016, p. 1-28.

Research output: Contribution to journalArticlepeer-review

Published

Documents

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
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 25434177