# Item

ITEM ACTIONSEXPORT

Released

Paper

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

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2005.11541.pdf

(Preprint), 703KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Künnemann, M., & Marx, D. (2020). Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction. Retrieved from https://arxiv.org/abs/2005.11541.

Cite as: https://hdl.handle.net/21.11116/0000-0007-492E-5

##### 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.

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.