hide
Free keywords:
Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
To study the question under which circumstances small solutions can be found
faster than by exhaustive search (and by how much), we study the fine-grained
complexity of Boolean constraint satisfaction with size constraint exactly $k$.
More precisely, we aim to determine, for any finite constraint family, the
optimal running time $f(k)n^{g(k)}$ required to find satisfying assignments
that set precisely $k$ of the $n$ variables to $1$.
Under central hardness assumptions on detecting cliques in graphs and
3-uniform hypergraphs, we give an almost tight characterization of $g(k)$ into
four regimes: (1) Brute force is essentially best-possible, i.e., $g(k) = (1\pm
o(1))k$, (2) the best algorithms are as fast as current $k$-clique algorithms,
i.e., $g(k)=(\omega/3\pm o(1))k$, (3) the exponent has sublinear dependence on
$k$ with $g(k) \in [\Omega(\sqrt[3]{k}), O(\sqrt{k})]$, or (4) the problem is
fixed-parameter tractable, i.e., $g(k) = O(1)$.
This yields a more fine-grained perspective than a previous FPT/W[1]-hardness
dichotomy (Marx, Computational Complexity 2005). Our most interesting technical
contribution is a $f(k)n^{4\sqrt{k}}$-time 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.
