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

Abstract

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\left({\left(dk/\epsilon \right)}^d\right)}\cdot (n+m{)}^{O(1)}$ for Max $k$-Weight SAT when the incidence graph is $K_{d,d}$-free. They asked whether a polynomial-size approximate kernel exists. In this work, we answer this question positively by giving an $(1-\epsilon )$-approximate kernel with ${\left(\frac{dk}{\epsilon }\right)}^{O(d)}$ variables. This also implies an improved FPT-AS with running time $(dk/\epsilon {)}^{O(dk)}\cdot (n+m{)}^{O(1)}$. Our approximate kernel is based mainly on a couple of greedy strategies together with a sunflower lemma-style reduction rule.

arXiv commentAdded a discussion on related independent work of Inamdar et al. (ICALP 2024)