Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
<|reference_start|>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\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{d k}{\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.<|reference_end|>
@article{manurangsi2024improved,
    title={Improved FPT Approximation Scheme and Approximate Kernel for
  Biclique-Free Max k-Weight SAT: Greedy Strikes Back},
    author={Pasin Manurangsi},
    journal={arXiv preprint arXiv:2403.06335},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.06335},
    primaryClass={cs.DS}
}