Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction

Under central hardness assumptions on detecting cliques in (hyper-)graphs, we give an almost tight characterization of g(k) into four regimes, giving a more fine-grained perspective than a previous FPT/W[1]-hardness dichotomy (Marx, Computational Complexity 2005). Our most interesting technical contribution is a subexponential-in-k algorithm for SubsetSum with precedence constraints parameterized by the target k -- particularly the approach, based on generalizing a bound on the Frobenius coin problem to a setting with precedence constraints, might be of independent interest.

This is joint work with Daniel Marx, appearing at CCC 2020 (https://arxiv.org/abs/2005.11541)