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 2O((dk/ε)ᵈ) · (n + m)O(1) for Max k-Weight SAT when the incidence graph is Kd,d-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.