Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back

In the Max k-Weight SAT (aka Max SAT with Cardinality Constraint) problem, we are given a CNF formula with n variables and m clauses together with a positive integer k. The goal is to find an assignment where at most k variables are set to one that satisfies as many constraints as possible. Recently, Jain et al. SODA'23 gave an FPT approximation scheme (FPT-AS) with running time 2^O ( (dk/) ᵈ) (n + m) ^O (1) for Max k-Weight SAT when the incidence graph is K₃, ₃-free. They asked whether a polynomial-size approximate kernel exists. In this work, we answer this question positively by giving an (1 -) -approximate kernel with (d k) ^O (d) variables. This also implies an improved FPT-AS with running time (dk/) ^O (dk) (n + m) ^O (1). Our approximate kernel is based mainly on a couple of greedy strategies together with a sunflower lemma-style reduction rule.