On MAX-SAT with Cardinality Constraint

We consider the weighted MAX-SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k-WMAX-SAT. This problem admits a (1 - 1/e)-factor approximation algorithm in polynomial time [Sviridenko, Algorithmica 2001] and it is proved that there is no (1 - 1/e + epsilon)-factor approximation algorithm in f(k) center dot n(o(k)) time for Maximum Coverage, the unweighted monotone version of k-WMAX-SAT [Manurangsi, SODA 2020]. Therefore, we study two restricted versions of the problem in the realm of parameterized complexity. 1. When the input is an unweighted 2-CNF formula (the problem is called k-MAX-2SAT), we design an efficient polynomial-size approximate kernelization scheme. That is, we design a polynomialtime algorithm that given a 2-CNF formula psi and epsilon > 0, compresses the input instance to a 2-CNF formula psi(star) such that any c-approximate solution of psi(star) can be converted to a c(1 - epsilon)-approximate solution of psi in polynomial time. 2. When the input is a planar CNF formula, i.e., the variable-clause incident graph is a planar graph, we show the following results: - There is an FPT algorithm for k-WMAX-SAT on planar CNF formulas that runs in 2(O(k)) center dot (C + V) time. - There is a polynomial-time approximation scheme for k-WMAX-SAT on planar CNF formulas that runs in time 2(O(1/epsilon))center dot k center dot (C + V). The above-mentioned C and V are the number of clauses and variables of the input formula respectively.